Faster graph coloring in polynomial space

DOI10.1007/s00453-022-01034-7OpenAlexW4302587030MaRDI QIDQ5925619

Serge Gaspers, Edward J. Lee

Publication date: 16 February 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01034-7

zbMATH Keywords

graph coloringanalysis of algorithmsexponential time algorithmscounting independent setsbranching algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Exact exponential algorithms.
• Enumerating maximal independent sets with applications to graph colouring.
• Exact algorithms for exact satisfiability and number of perfect matchings
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• A note on the complexity of the chromatic number problem
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Counting models for 2SAT and 3SAT formulae
• Open problems around exact algorithms
• On the hardness of approximate reasoning
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Counting Maximal Independent Sets in Subcubic Graphs
• A measure & conquer approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Set Partitioning via Inclusion-Exclusion
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Separate, Measure and Conquer
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Worst-case time bounds for coloring and satisfiability problems
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• An algorithm for the chromatic number of a graph
• Recent Advances in Constraints
• Faster graph coloring in polynomial space

This page was built for publication: Faster graph coloring in polynomial space