Skip to content
naulon
Not checkedNot checked for notices yet.

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 references

    Reads

    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.