Quantum Algorithm for the Longest Trail Problem

Autor:	Khadiev, Kamil, Kapralov, Ruslan
Rok vydání:	2021
Předmět:	Quantum Physics Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	We present the quantum algorithm for the Longest Trail Problem. The problem is to search the longest edge-simple path for a graph with $n$ vertexes and $m$ edges. Here edge-simple means no edge occurs in the path twice, but vertexes can occur several times. The running time of our algorithm is $O^*(1.728^m)$. Comment: RuFiDim 2021. arXiv admin note: substantial text overlap with arXiv:2112.13319
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2112.13847 Zobrazit plný text záznamu View this record from Arxiv