Counting the number of independent sets in chordal graphs

DOI10.1016/j.jda.2006.07.006zbMath1146.05029OpenAlexW2151864939MaRDI QIDQ935840

Takeaki Uno, Yoshio Okamoto, Ryuhei Uehara

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.07.006

zbMATH Keywords

enumerationpolynomial time algorithmNP-completenesscountingindependent setchordal graph\#P-completeness

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Balanced independent and dominating sets on colored interval graphs, Counting and sampling orientations on chordal graphs, Linear-time algorithms for counting independent sets in bipartite permutation graphs, On independent sets and bicliques in graphs, Counting independent sets in tricyclic graphs, Maximal independent sets in grid graphs, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Computing role assignments of proper interval graphs in polynomial time, Fair cost allocations under conflicts - a game-theoretic point of view -, Counting independent sets in cocomparability graphs, Counting independent sets in a tolerance graph, Listing Maximal Independent Sets with Minimal Space and Bounded Delay, Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width, Computing role assignments of chordal graphs, Counting maximal independent sets in directed path graphs, Counting the number of vertex covers in a trapezoid graph, A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number, Counting independent sets in tree convex bipartite graphs, Maximal independent sets in caterpillar graphs, Counting and enumerating independent sets with applications to combinatorial optimization problems, Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent domination in chordal graphs
• Efficient graph representations
• A characterisation of rigid circuit graphs
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Algorithmic graph theory and perfect graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Incidence matrices and interval graphs
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the Desirability of Acyclic Database Schemes
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A threshold of ln n for approximating set cover
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• The Parameterized Complexity of Counting Problems
• Efficient Parallel Algorithms for Chordal Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Graph-Theoretic Concepts in Computer Science