Fast algorithms for solving the Hamilton cycle problem with high probability
Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.
Download (ext.)
https://doi.org/10.48550/arXiv.2111.14759
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Abstract
We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different 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 two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting.
Publishing Year
Date Published
2023-01-01
Proceedings Title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Volume
2023
Page
2286-2323
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Florence, Italy
Conference Date
2023-01-22 – 2023-01-25
ISBN
IST-REx-ID
Cite this
Anastos M. Fast algorithms for solving the Hamilton cycle problem with high probability. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:10.1137/1.9781611977554.ch88
Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem with high probability. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch88
Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2023:2286–2323. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/1.9781611977554.ch88.
M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high probability,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Florence, Italy, 2023, vol. 2023, pp. 2286–2323.
Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.
Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2023, Society for Industrial and Applied Mathematics, 2023, pp. 2286–323, doi:10.1137/1.9781611977554.ch88.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2111.14759