Permutation Graphs: Connected Domination and Steiner Trees

Charles J. Colbourn; Lorna K. Stewart

doi:10.1016/S0167-5060(08)71048-3

Permutation Graphs: Connected Domination and Steiner Trees

Charles J. Colbourn
, Lorna K. Stewart

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

5 Scopus citations

Abstract

Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

Original language	English (US)
Pages (from-to)	179-189
Number of pages	11
Journal	Annals of Discrete Mathematics
Volume	48
Issue number	C
DOIs	https://doi.org/10.1016/S0167-5060(08)71048-3
State	Published - Jan 1 1991
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0167-5060(08)71048-3

Cite this

@article{6163e3f795364f5ab128ee0a30870741,

title = "Permutation Graphs: Connected Domination and Steiner Trees",

abstract = "Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.",

author = "Colbourn, \{Charles J.\} and Stewart, \{Lorna K.\}",

note = "Funding Information: Research of the first author is supported by NSERC Canada under grant number A0579. Thanks are due to both referees for suggesting improvements in the presentation.",

year = "1991",

month = jan,

day = "1",

doi = "10.1016/S0167-5060(08)71048-3",

language = "English (US)",

volume = "48",

pages = "179--189",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - Permutation Graphs

T2 - Connected Domination and Steiner Trees

AU - Colbourn, Charles J.

AU - Stewart, Lorna K.

N1 - Funding Information: Research of the first author is supported by NSERC Canada under grant number A0579. Thanks are due to both referees for suggesting improvements in the presentation.

PY - 1991/1/1

Y1 - 1991/1/1

N2 - Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

AB - Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

UR - https://www.scopus.com/pages/publications/77957813269

UR - https://www.scopus.com/pages/publications/77957813269#tab=citedBy

U2 - 10.1016/S0167-5060(08)71048-3

DO - 10.1016/S0167-5060(08)71048-3

M3 - Article

AN - SCOPUS:77957813269

SN - 0167-5060

VL - 48

SP - 179

EP - 189

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

IS - C

ER -

Permutation Graphs: Connected Domination and Steiner Trees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this