Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
DOI10.1016/J.DAM.2017.12.023zbMATH Open1382.05034OpenAlexW2783719167MaRDI QIDQ1706124FDOQ1706124
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
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
independent setslinear-time algorithmscounting problemdistance-hereditary graphsindependent dominating setsindependent perfect dominating sets
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)
Cites Work
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- On the clique-width of some perfect graph classes
- Distance-hereditary graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Weighted efficient domination problem on some perfect graphs
- Computing maximum stable sets for distance-hereditary graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Counting the number of vertex covers in a trapezoid graph
- Completely separable graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Counting the number of independent sets in chordal graphs
- Counting maximal independent sets in directed path graphs
- Counting independent sets in a tolerance graph
- Fast and simple algorithms to count the number of vertex covers in an interval graph
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Counting independent sets in tree convex bipartite graphs
- Domination in distance-hereditary graphs
Cited In (5)
- Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
- An exact enumeration of distance-hereditary graphs
- Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
- Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks
- Computing maximum stable sets for 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)
