Counting maximal independent sets in directed path graphs

DOI10.1016/J.IPL.2014.05.003MaRDI QIDQ2015155zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

counting problemmaximal independent setsdirected 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)

Recommendations

• Counting the number of independent sets in chordal graphs
• Graph-Theoretic Concepts in Computer Science
• Counting independent sets in a tolerance graph
• Counting the maximal independent sets in power set graphs
• Counting independent sets in cocomparability graphs

Cites work

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

Cited in

(11)

• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Directed path graph isomorphism
• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• Counting independent sets in graphs with bounded bipartite pathwidth
• Counting the number of independent sets in chordal graphs
• Counting maximal distance-independent sets in grid graphs
• Counting independent sets in cocomparability graphs
• Counting the maximal independent sets in power set graphs
• Graph-Theoretic Concepts in Computer Science
• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• Counting independent sets in a tolerance graph

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)