Fast algorithms for solving the Hamilton Cycle problem with high\n probability

2021/11/29 by Michael Anastos, Anastos, Michael
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Genome Rearrangement Algorithms #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.2111.14759

Abstract

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

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\n Random Graphs