Simple linear-time algorithms for counting independent sets in distance-hereditary graphs

DOI10.1016/j.dam.2017.12.023zbMath1382.05034OpenAlexW2783719167MaRDI QIDQ1706124

Min-Sheng Lin

Publication date: 21 March 2018

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

Full work available at URL: https://doi.org/10.1016/j.dam.2017.12.023

zbMATH Keywords

distance-hereditary graphsindependent setscounting problemlinear-time algorithmsindependent dominating setsindependent perfect dominating sets

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks ⋮ Fast and simple algorithms for counting dominating sets in distance-hereditary graphs

Cites Work

• Counting independent sets in a tolerance graph
• Counting independent sets in tree convex bipartite graphs
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Completely separable graphs
• Counting the number of independent sets in chordal graphs
• Counting the number of vertex covers in a trapezoid graph
• Distance-hereditary graphs
• Weighted efficient domination problem on some perfect graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Counting maximal independent sets in directed path graphs
• Computing maximum stable sets for distance-hereditary graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• The Complexity of Enumeration and Reliability Problems
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Domination in distance-hereditary graphs

This page was built for publication: Simple linear-time algorithms for counting independent sets in distance-hereditary graphs