Fast algorithms for solving the Hamilton Cycle problem with high probability

2021/11/29 by Michael Anastos, Anastos, Michael
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #DNA and Biological Computing #Genome Rearrangement Algorithms #cs.DM #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.2111.14759

arxiv created 2021/11/29 · arxiv updated 2021/11/30

Abstract

We study the Hamilton cycle problem with input a random graph G=G(n,p) in two settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one we are given the adjacency matrix of G. In each of the settings we give a deterministic algorithm that w.h.p. either it finds a Hamilton cycle or it returns a certificate that such a cycle does not exists, for p > 0. The running times of our algorithms are w.h.p. O(n) and O(n/p) respectively each being best possible in its own setting.

Related

• An O(n) time algorithm for finding Hamilton cycles with high probability
• Finding a Hamilton cycle fast on average using rotations and extensions
• Finding Hamilton cycles in random graphs with few queries
• A fast algorithm on average for solving the Hamilton Cycle problem
• Fast and Efficient Distributed Computation of Hamiltonian Cycles in Random Graphs