A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs

DOI<177::AID-NET4>3.0.CO;2-C 10.1002/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-CzbMath0990.05116OpenAlexW2059518216MaRDI QIDQ4540045

Andreas Brandstädt, Feodor F. Dragan

Publication date: 21 July 2002

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199805)31:3<177::aid-net4>3.0.co;2-c

zbMATH Keywords

distance-hereditary graphSteiner treeconnected dominationlabeling algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Weighted efficient domination problem on some perfect graphs, Networks with small stretch number, The \(k\)-hop connected dominating set problem: approximation and hardness, Homogeneously orderable graphs, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, A note on connected dominating sets of distance-hereditary graphs, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs, Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way, Equistable distance-hereditary graphs, Graphs with bounded induced distance, Distance-hereditary comparability graphs, The Hamiltonian problem on distance-hereditary graphs, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, Domination in distance-hereditary graphs, Weighted connected domination and Steiner trees in distance-hereditary graphs, Laminar structure of ptolemaic graphs with applications, Unnamed Item, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES, Fast and simple algorithms for counting dominating sets in distance-hereditary graphs