Counting Maximal Independent Sets in Subcubic Graphs

DOI10.1007/978-3-642-27660-6_27zbMath1302.05192MaRDI QIDQ2891379

Konstanty Junosza-Szaniawski, Michał Tuczyński

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_27

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Maximal independent sets in grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• 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
• Counting Independent Sets in Claw-Free Graphs
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Set Partitioning via Inclusion-Exclusion
• On Independent Sets and Bicliques in Graphs
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Computing minimal models, stable models and answer sets