Counting maximal independent sets in directed path graphs

DOI10.1016/j.ipl.2014.05.003zbMath1371.68119OpenAlexW2016277208MaRDI QIDQ2015155

Sheng-Huang Su, Min-Sheng Lin

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

zbMATH Keywords

maximal independent setscounting problemdirected path graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Counting independent sets in a tolerance graph

Cites Work

• The complexity of computing the permanent
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting the number of independent sets in chordal graphs
• Counting the number of vertex covers in a trapezoid graph
• Intersection graphs of paths in a tree
• Trapezoid graphs and their coloring
• Comparability graphs and intersection graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Number of Maximal Independent Sets in a Tree
• The Complexity of Enumeration and Reliability Problems
• Permutation Graphs and Transitive Graphs

This page was built for publication: Counting maximal independent sets in directed path graphs