Counting Maximal Independent Sets in Subcubic Graphs

DOI10.1007/978-3-642-27660-6_27zbMATH Open1302.05192OpenAlexW111187085MaRDI QIDQ2891379FDOQ2891379

Authors: 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

Recommendations

• The maximum independent set problem in subclasses of subcubic graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Counting the maximal independent sets in power set graphs
• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• The number of maximum independent sets in graphs
• On the number of maximal independent sets in a graph
• On the number of maximum independent sets of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Exact exponential algorithms.
• On two techniques of combining branching and treewidth
• Counting models for 2SAT and 3SAT formulae
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Set partitioning via inclusion-exclusion
• The complexity of counting in sparse, regular, and planar graphs
• Pathwidth of cubic graphs and exact algorithms
• New methods for 3-SAT decision and worst-case analysis
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• On Independent Sets and Bicliques in Graphs
• Title not available (Why is that?)
• Computing minimal models, stable models and answer sets
• New upper bound for the \#3-SAT problem
• Title not available (Why is that?)
• Counting independent sets in claw-free graphs

Cited In (5)

• Independent sets and matchings in subcubic graphs
• Maximal independent sets in grid graphs
• The maximum independent set problem in subclasses of subcubic graphs
• Faster graph coloring in polynomial space
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs

This page was built for publication: Counting Maximal Independent Sets in Subcubic Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891379)