Permutation Graphs: Connected Domination and Steiner Trees

Charles J. Colbourn, Lorna K. Stewart

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 languageEnglish (US)
Pages (from-to)179-189
Number of pages11
JournalAnnals of Discrete Mathematics
Issue numberC
StatePublished - Jan 1 1991
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Permutation Graphs: Connected Domination and Steiner Trees'. Together they form a unique fingerprint.

Cite this