Premium
Steiner trees, connected domination and strongly chordal graphs
Author(s) -
White Kevin,
Farber Martin,
Pulleyblank William
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150109
Subject(s) - chordal graph , steiner tree problem , dominating set , mathematics , combinatorics , cardinality (data modeling) , pathwidth , treewidth , discrete mathematics , indifference graph , graph , computer science , vertex (graph theory) , line graph , data mining
We consider Steiner tree problems and connected dominating set problems for several classes of graphs. We give a polynomial algorithm and a min‐max theorem for the cardinality Steiner problem in strongly chordal graphs and a polynomial algorithm for the weighted connected dominating set problem in series‐parallel graphs. We establish simple direct transformations between Steiner problems and connected domination problems for several classes of graphs and establish related NP ‐completeness results.