Permutation graphs: Connected domination and Steiner trees

Charles J. Colbourn, Lorna K. Stewart

Research output: Contribution to journalArticlepeer-review

44 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
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Dec 14 1990
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • 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