Weighted connected domination and Steiner trees in distance-hereditary graphs

DOI10.1016/S0166-218X(98)00060-2zbMath0906.05030WikidataQ126777906 ScholiaQ126777906MaRDI QIDQ1270785

Hong-Gwa Yeh, Gerard Jennhwa Chang

Publication date: 1 February 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

linear time algorithmdistance-hereditary graphSteiner treeconnected domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (10)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Unique response Roman domination: complexity and algorithms ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ Paired-domination problem on distance-hereditary 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 ⋮ The \(k\)-power domination problem in weighted trees ⋮ Linear separation of connected dominating sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Completely separable graphs
• Clustering and domination in perfect graphs
• Distance-hereditary graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Labeling algorithms for domination problems in sun-free chordal graphs
• Complement reducible graphs
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• The Steiner tree problem
• Weighted independent perfect domination on cocomparability graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• The traveling salesman problem on a graph and some related integer polyhedra
• A Linear Recognition Algorithm for Cographs
• Steiner trees, connected domination and strongly chordal graphs
• On finding spanning eulerian subgraphs
• The NP-completeness column: an ongoing guide
• The node-weighted steiner tree problem
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• R -Domination in Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Steiner Distance-Hereditary Graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs

This page was built for publication: Weighted connected domination and Steiner trees in distance-hereditary graphs