Steiner trees, connected domination and strongly chordal graphs
Copyright policy )Steiner trees, connected domination and strongly chordal graphs
AbstractWe 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.
- University of Waterloo Canada
Graph theory, Steiner tree problems, NP-completeness results, Graph theory (including graph drawing) in computer science, polynomial algorithm, series-parallel graphs, chordal graphs, Trees, connected dominating set problems
Graph theory, Steiner tree problems, NP-completeness results, Graph theory (including graph drawing) in computer science, polynomial algorithm, series-parallel graphs, chordal graphs, Trees, connected dominating set problems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).89 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!