Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs

DOI10.1016/S0304-3975(00)00225-5zbMath0972.05038MaRDI QIDQ5941496

Gerard Jennhwa Chang, Hong-Gwa Yeh

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algorithm\(k\)-dominating cliqueconnected \(k\)-dominationdistance-hereditary graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Networks with small stretch number ⋮ A note on connected dominating sets of distance-hereditary graphs ⋮ Distance-hereditary comparability graphs ⋮ The Hamiltonian problem on distance-hereditary graphs ⋮ Domination in distance-hereditary graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• Completely separable graphs
• Distance-hereditary graphs
• On domination problems for permutation and other graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• Dominating cliques in chordal graphs
• Algorithmic aspects of majority domination
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Domination on Cocomparability Graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The NP-completeness column: an ongoing guide
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• Dominating cliques in graphs

This page was built for publication: Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs