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.
No takes yet. Share an insight, caveat, or question.
White et al. (1985) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: