On computing graph closures

Samir Khuller

doi:10.1016/0020-0190(89)90082-3

On computing graph closures

Samir Khuller^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	249-255
Number of pages	7
Journal	Information Processing Letters
Volume	31
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(89)90082-3
State	Published - Jun 12 1989

Keywords

P-completeness
closure
graphs

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(89)90082-3

Cite this

@article{707780fb51c14aa78e925b5c416827bd,

title = "On computing graph closures",

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.",

keywords = "P-completeness, closure, graphs",

author = "Samir Khuller",

note = "Funding Information: * Supported by NSF Grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.",

year = "1989",

month = jun,

day = "12",

doi = "10.1016/0020-0190(89)90082-3",

language = "English (US)",

volume = "31",

pages = "249--255",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - On computing graph closures

AU - Khuller, Samir

N1 - Funding Information: * Supported by NSF Grant DCR 85-52938 and PYI matching funds from AT&T Bell Labs.

PY - 1989/6/12

Y1 - 1989/6/12

N2 - 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.

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.

KW - P-completeness

KW - closure

KW - graphs

UR - http://www.scopus.com/inward/record.url?scp=0024680414&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024680414&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(89)90082-3

DO - 10.1016/0020-0190(89)90082-3

M3 - Article

AN - SCOPUS:0024680414

SN - 0020-0190

VL - 31

SP - 249

EP - 255

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On computing graph closures

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this