TY - JOUR T1 - On computing graph closures JF - Information Processing Letters Y1 - 1989 A1 - Khuller, Samir KW - closure KW - graphs KW - P-completeness AB - The closure of a graph G of n vertices is obtained from G by recursively joining pairs of non-adjacent vertices whose degree sum is at least n until no such pair remains. We give an efficient algorithm to compute the closure using F-heaps. We also define the general closure of a graph and show that computing the general closure is P-complete with respect to log-space transformations. VL - 31 SN - 0020-0190 UR - http://www.sciencedirect.com/science/article/pii/0020019089900823 CP - 5 M3 - 10.1016/0020-0190(89)90082-3 ER -