A Grover Search-Based Algorithm for the List Coloring Problem
Sayan Mukherjee
IEEE Transactions on Quantum Engineering · 2022
doi:10.1109/tqe.2022.3151137 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-coloring of graphs on <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> vertices has runtimes <inline-formula><tex-math notation="LaTeX">$\Omega (2^n)$</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">$k\geq 5$</tex-math></inline-formula>. The list coloring problem asks the following more general question: given a <italic>list</italic> of available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.
Abstract licence: CC BY-NC-ND
References46
40 more references, whose wording the paper’s licence keeps private.
All 46 referencesReads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.