Efficient algorithms for interval graphs and circular‐arc graphs

U. I. Gupta; D. T. Lee; J. Y.‐T Leung

doi:10.1002/net.3230120410

Efficient algorithms for interval graphs and circular‐arc graphs

U. I. Gupta, D. T. Lee, J. Y.‐T Leung

Research output: Contribution to journal › Article › peer-review

211 Scopus citations

Abstract

We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n²) time, provided again that a corresponding family of arcs is given.

Original language	English (US)
Pages (from-to)	459-467
Number of pages	9
Journal	Networks
Volume	12
Issue number	4
DOIs	https://doi.org/10.1002/net.3230120410
State	Published - 1982
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Networks and Communications

Access to Document

10.1002/net.3230120410

Cite this

@article{5185a83706fd4d50b821f69537875d79,

title = "Efficient algorithms for interval graphs and circular‐arc graphs",

abstract = "We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.",

author = "Gupta, {U. I.} and Lee, {D. T.} and Leung, {J. Y.‐T}",

year = "1982",

doi = "10.1002/net.3230120410",

language = "English (US)",

volume = "12",

pages = "459--467",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Efficient algorithms for interval graphs and circular‐arc graphs

AU - Gupta, U. I.

AU - Lee, D. T.

AU - Leung, J. Y.‐T

PY - 1982

Y1 - 1982

N2 - We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.

AB - We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n2) time, provided again that a corresponding family of arcs is given.

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

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

U2 - 10.1002/net.3230120410

DO - 10.1002/net.3230120410

M3 - Article

AN - SCOPUS:0020246926

SN - 0028-3045

VL - 12

SP - 459

EP - 467

JO - Networks

JF - Networks

IS - 4

ER -

Efficient algorithms for interval graphs and circular‐arc graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this