Fast and simple algorithms for counting dominating sets in distance-hereditary graphs

DOI10.1142/S1793830921500129zbMath1475.05162OpenAlexW3081529052MaRDI QIDQ5012812

Min-Sheng Lin

Publication date: 25 November 2021

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830921500129

zbMATH Keywords

algorithmsdistance-hereditary graphscounting problemdominating sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Counting dominating sets in some subclasses of bipartite graphs

Cites Work

• Distance-hereditary graphs
• Weighted efficient domination problem on some perfect graphs
• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• The Hamiltonian problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Computing maximum stable sets for distance-hereditary graphs
• Dominating Set Counting in Graph Classes
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• The Complexity of Enumeration and Reliability Problems
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• The Complexity of Planar Counting Problems
• Graph Classes: A Survey
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Domination in distance-hereditary graphs

This page was built for publication: Fast and simple algorithms for counting dominating sets in distance-hereditary graphs