𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Weighted connected domination and Steiner trees in distance-hereditary graphs

✍ Scribed by Yeh Hong-Gwa; Gerard J. Chang

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
649 KB
Volume
87
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted connected dominating set and a minimum vertex-weighted Steiner tree in a distance-hereditary graph. Both problems are MY-complete in general graphs.

πŸ“œ SIMILAR VOLUMES

Permutation graphs: Connected domination
Permutation graphs: Connected domination and Steiner trees
✍ Charles J. Colbourn; Lorna K. Stewart πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 702 KB

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.

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ BrandstοΏ½dt, Andreas; Dragan, Feodor F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree