Solving the Hamilton cycle problem fast on average
Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022–October, 919–930.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Abstract
We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥
100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and
Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n
−1/2 respectively.
Publishing Year
Date Published
2022-12-01
Proceedings Title
63rd Annual IEEE Symposium on Foundations of Computer Science
Publisher
Institute of Electrical and Electronics Engineers
Acknowledgement
This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant
agreement No 101034413
Volume
2022-October
Page
919-930
Conference
FOCS: Symposium on Foundations of Computer Science
Conference Location
Denver, CO, United States
Conference Date
2022-10-31 – 2022-11-03
ISBN
ISSN
IST-REx-ID
Cite this
Anastos M. Solving the Hamilton cycle problem fast on average. In: 63rd Annual IEEE Symposium on Foundations of Computer Science. Vol 2022-October. Institute of Electrical and Electronics Engineers; 2022:919-930. doi:10.1109/FOCS54457.2022.00091
Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In 63rd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022–October, pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/FOCS54457.2022.00091
Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” In 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022–October:919–30. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/FOCS54457.2022.00091.
M. Anastos, “Solving the Hamilton cycle problem fast on average,” in 63rd Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United States, 2022, vol. 2022–October, pp. 919–930.
Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022–October, 919–930.
Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” 63rd Annual IEEE Symposium on Foundations of Computer Science, vol. 2022–October, Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:10.1109/FOCS54457.2022.00091.
Export
Marked PublicationsOpen Data ISTA Research Explorer
Google Scholar
ISBN Search