Counting maximal independent sets in directed path graphs
From MaRDI portal
Publication:2015155
DOI10.1016/J.IPL.2014.05.003zbMATH Open1371.68119OpenAlexW2016277208MaRDI QIDQ2015155FDOQ2015155
Authors: Min-Sheng Lin, Sheng-Huang Su 
Publication date: 23 June 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2014.05.003
Recommendations
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- The complexity of computing the permanent
- Intersection graphs of paths in a tree
- Comparability graphs and intersection graphs
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Trapezoid graphs and their coloring
- Permutation Graphs and Transitive Graphs
- Counting the number of vertex covers in a trapezoid graph
- The Number of Maximal Independent Sets in a Tree
- Counting the number of independent sets in chordal graphs
- Fast and simple algorithms to count the number of vertex covers in an interval graph
Cited In (5)
- Counting independent sets in graphs with bounded bipartite pathwidth
- Counting the number of independent sets in chordal graphs
- Counting independent sets in a tolerance graph
- Graph-Theoretic Concepts in Computer Science
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
This page was built for publication: Counting maximal independent sets in directed path graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015155)
