Counting Independent Sets in Claw-Free Graphs

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

zbMATH Keywords

counting problems

Mathematics Subject Classification ID

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 (1)

Counting Maximal Independent Sets in Subcubic Graphs

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

This page was built for publication: Counting Independent Sets in Claw-Free Graphs