A Grover Search-Based Algorithm for the List Coloring Problem
Publication
, Journal Article
Mukherjee, S
Published in: IEEE Transactions on Quantum Engineering
January 1, 2022
Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for k-coloring of graphs on n vertices has runtimes Ω (2n) for ≥ 5. The list coloring problem asks the following more general question: given a list 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.
Altmetric Attention Stats
Dimensions Citation Stats
Published In
IEEE Transactions on Quantum Engineering
DOI
EISSN
2689-1808
Publication Date
January 1, 2022
Volume
3
Citation
APA
Chicago
ICMJE
MLA
NLM
Mukherjee, S. (2022). A Grover Search-Based Algorithm for the List Coloring Problem. IEEE Transactions on Quantum Engineering, 3. https://doi.org/10.1109/TQE.2022.3151137
Mukherjee, S. “A Grover Search-Based Algorithm for the List Coloring Problem.” IEEE Transactions on Quantum Engineering 3 (January 1, 2022). https://doi.org/10.1109/TQE.2022.3151137.
Mukherjee S. A Grover Search-Based Algorithm for the List Coloring Problem. IEEE Transactions on Quantum Engineering. 2022 Jan 1;3.
Mukherjee, S. “A Grover Search-Based Algorithm for the List Coloring Problem.” IEEE Transactions on Quantum Engineering, vol. 3, Jan. 2022. Scopus, doi:10.1109/TQE.2022.3151137.
Mukherjee S. A Grover Search-Based Algorithm for the List Coloring Problem. IEEE Transactions on Quantum Engineering. 2022 Jan 1;3.
Published In
IEEE Transactions on Quantum Engineering
DOI
EISSN
2689-1808
Publication Date
January 1, 2022
Volume
3