Counting Independent Sets in Claw-Free Graphs
DOI10.1007/978-3-642-25870-1_21zbMath1341.05191MaRDI 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
05C30: Enumeration in graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
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