Exact algorithms for counting 3-colorings of graphs

DOI10.1016/j.dam.2022.08.002zbMath1498.05262OpenAlexW4292429776MaRDI QIDQ2081467

Zehui Shao, Pu Wu, En-Qiang Zhu

Publication date: 13 October 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.08.002

zbMATH Keywords

dynamic programmingbranch and reducemeasure and conquerexact exponential-time algorithms

Mathematics Subject Classification ID

Dynamic programming (90C39) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• Exact exponential algorithms.
• Enumerating maximal independent sets with applications to graph colouring.
• On two techniques of combining branching and treewidth
• A note on the complexity of the chromatic number problem
• Graph multi-coloring for a job scheduling application
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Exact algorithms for maximum independent set
• Inclusion/exclusion meets measure and conquer
• Fast algorithms for max independent set
• Open problems around exact algorithms
• Parametrized complexity theory.
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A measure & conquer approach for the analysis of exact algorithms
• The Mathematical Coloring Book
• Set Partitioning via Inclusion-Exclusion
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Graph minors. II. Algorithmic aspects of tree-width
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• 3-coloring in time
• An Algorithm for the Chromatic Number of a Graph
• Reducibility among Combinatorial Problems
• Exact Algorithms via Monotone Local Search
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• A Computing Procedure for Quantification Theory
• An algorithm for the chromatic number of a graph
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Exact algorithms for counting 3-colorings of graphs