2
[2111.14759] Fast algorithms for solving the Hamilton Cycle problem with high pr...
source link: https://arxiv.org/abs/2111.14759
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 29 Nov 2021]
Fast algorithms for solving the Hamilton Cycle problem with high probability
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.
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2111.14759 [math.CO] |
| (or arXiv:2111.14759v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2111.14759 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK