Exponential-time quantum algorithms for graph coloring problems

DOI10.1007/s00453-022-00976-2OpenAlexW2953580776WikidataQ115606745 ScholiaQ115606745MaRDI QIDQ5970782

Ryuhei Mori, Kazuya Shimizu

Publication date: 8 December 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00976-2

zbMATH Keywords

dynamic programminggraph coloringquantum algorithmGrover's search

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• Enumerating maximal independent sets with applications to graph colouring.
• Exact algorithms for exact satisfiability and number of perfect matchings
• A note on the complexity of the chromatic number problem
• Quantum Random Access Memory
• Set Partitioning via Inclusion-Exclusion
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• 3-coloring in time
• On Problems as Hard as CNF-SAT
• Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
• Solving NP-Complete Problems with Quantum Search
• Faster graph coloring in polynomial space

This page was built for publication: Exponential-time quantum algorithms for graph coloring problems