Constructing Hamilton cycles and perfect matchings efficiently
EUROCOMB’23
36–41
Miklós Ajtai, János Komlós, and Endre Szemerédi. First occurrence of Hamilton cycles in random graphs. North-Holland Mathematics Studies, 115(C):173-178, 1985.
https://doi.org/10.1016/S0304-0208(08)73007-X
Michael Anastos. A note on long cycles in sparse random graphs. The Electronic Journal of Combinatorics 30.2, 2023.
https://doi.org/10.37236/11471
Michael Anastos and Alan Frieze. A scaling limit for the length of the longest cycle in a sparse random graph. Journal of Combinatorial Theory, Series B, 148:184-208, 2021.
https://doi.org/10.1016/j.jctb.2021.01.001
Tom Bohman and Alan Frieze. Avoiding a giant component. Random Structures & Algorithms, 19(1):75-85, 2001.
https://doi.org/10.1002/rsa.1019
Tom Bohman and Alan Frieze. Hamilton cycles in 3-out. Random Structures & Algorithms, 35(4):393-417, 2009.
https://doi.org/10.1002/rsa.20272
Béla Bollobás. The evolution of sparse graphs, graph theory and combinatorics, 1984. MR, 777163(2):35-57, 1984.
Alan Frieze. Hamilton cycles in random graphs: a bibliography. arXiv preprint arXiv:1901.07139, 2019.
Alan Frieze and Michal Karoński. Introduction to random graphs. Cambridge Univer- sity Press, 2016.
https://doi.org/10.1017/CBO9781316339831
Alan Frieze, Michael Krivelevich, and Peleg Michaeli. Fast construction on a restricted budget. arXiv preprint arXiv:2207.07251, 2022.
János Komlós and Endre Szemerédi. Limit distribution for the existence of Hamilto- nian cycles in a random graph. Discrete mathematics, 43(1):55-63, 1983.
https://doi.org/10.1016/0012-365X(83)90021-3
Aleksei Dmitrievich Korshunov. Solution of a problem of Erdős and Rényi on Hamil- tonian cycles in nonoriented graphs. In Doklady Akademii Nauk, volume 228, pages 529-532. Russian Academy of Sciences, 1976.
Michael Krivelevich, Eyal Lubetzky, and Benny Sudakov. Hamiltonicity thresholds in achlioptas processes. Random Structures & Algorithms, 37(1):1-24, 2010.
https://doi.org/10.1002/rsa.20302
Lajos Pósa. Hamiltonian circuits in random graphs. Discrete Mathematics, 14(4):359- 364, 1976.
https://doi.org/10.1016/0012-365X(76)90068-6
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Michael Anastos