On computing graph closures

Samir Khuller*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)249-255
Number of pages7
JournalInformation Processing Letters
Volume31
Issue number5
DOIs
StatePublished - Jun 12 1989

Keywords

  • P-completeness
  • closure
  • graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'On computing graph closures'. Together they form a unique fingerprint.

Cite this