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

DOI10.1016/J.DAM.2017.12.023MaRDI QIDQ1706124zbMATH OpenOpenAlexFDO

Authors 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

independent setslinear-time algorithmscounting problemdistance-hereditary graphsindependent dominating setsindependent perfect dominating sets

Mathematics Subject Classification ID

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

Recommendations

• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• scientific article; zbMATH DE number 815104
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• scientific article; zbMATH DE number 841632

Cites work

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

Cited in

(5)

• 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
• Computing maximum stable sets for distance-hereditary graphs
• An exact enumeration of distance-hereditary graphs
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs

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

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