Very fast construction of bounded-degree spanning graphs via the semi-random graph process

DOI10.1137/1.9781611975994.44zbMath1497.68366arXiv1907.08031OpenAlexW3001179876MaRDI QIDQ5146812

Michael Krivelevich, Dan Hefetz, Omri Ben-Eliezer, Lior Gishboliner

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.08031

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)

Related Items (4)

Power of \(k\) choices in the semi-random graph process ⋮ Sharp thresholds in adaptive random graph processes ⋮ Hamilton cycles in the semi-random graph process ⋮ Perfect Matchings in the Semirandom Graph Process

This page was built for publication: Very fast construction of bounded-degree spanning graphs via the semi-random graph process