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

DOI10.1002/NET.1zbMath0974.05060OpenAlexW2081121429MaRDI QIDQ2719843

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 graphsgraph algorithmsdominating setdominationmodular decomposition

Mathematics Subject Classification ID

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

Related Items (9)

Unique response Roman domination: complexity and algorithms ⋮ Complexity results on cosecure domination in graphs ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Distance-hereditary digraphs ⋮ Domination in distance-hereditary graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Domination problems on P₅-free graphs

Cites Work

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

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