%0 Journal Article %J Information Processing Letters %D 1989 %T On computing graph closures %A Khuller, Samir %K closure %K graphs %K P-completeness %X 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. %B Information Processing Letters %V 31 %P 249 - 255 %8 1989/06/12/ %@ 0020-0190 %G eng %U http://www.sciencedirect.com/science/article/pii/0020019089900823 %N 5 %R 10.1016/0020-0190(89)90082-3