Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs

DOI10.1002/NET.1MaRDI QIDQ2719843zbMATH OpenOpenAlexFDO

Authors Falk Nicolai, Thomas Szymczak

Publication date 9 December 2001

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.1

zbMATH Keywords

distance-hereditary graphsdominating setdominationgraph algorithmsmodular decomposition

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• r-Domination problems on homogeneously orderable graphs
• Publication:4934237
• Paired-domination problem on distance-hereditary graphs

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Distance-hereditary graphs
• Dually Chordal Graphs
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Homogeneously orderable graphs
• r-domination problems on homogeneously orderable graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Total domination and transformation

Cited in

(15)

• Laminar structure of ptolemaic graphs with applications
• Dominating sets reconfiguration under token sliding
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• scientific article; zbMATH DE number 1389817 (Why is no real title available?)
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• Domination problems on \(P_{5}\)-free graphs
• Domination in distance-hereditary graphs
• Unique response Roman domination: complexity and algorithms
• Complexity results on cosecure domination in graphs
• Homogeneous sets and domination problems
• Hardness results and approximability of cosecure domination in graphs
• Distance-hereditary digraphs

This page was built for publication: Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719843)