Counting Independent Sets in Claw-Free Graphs
Publication:3104779
DOI10.1007/978-3-642-25870-1_21zbMath1341.05191OpenAlexW64736712MaRDI QIDQ3104779
Zbigniew Lonc, Konstanty Junosza-Szaniawski, Michał Tuczyński
Publication date: 16 December 2011
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_21
Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Counting models for 2SAT and 3SAT formulae
- New methods for 3-SAT decision and worst-case analysis
- New upper bound for the \#3-SAT problem
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Set Partitioning via Inclusion-Exclusion
- Computing minimal models, stable models and answer sets
- Automata, Languages and Programming