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

DOI10.1002/rsa.20963zbMath1497.68365OpenAlexW3090469133MaRDI QIDQ3386520

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

Publication date: 5 January 2021

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20963

zbMATH Keywords

embedding spanning graphssemi-random graph process

Mathematics Subject Classification ID

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

Related Items

Sharp thresholds in adaptive random graph processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Achlioptas process phase transitions are continuous
• Small subgraphs in random graphs and the power of multiple choices
• Hamilton connected graphs
• A geometric Achlioptas process
• Birth control for giants
• Spanning trees in random graphs
• Avoiding a giant component
• The Bohman-Frieze process near criticality
• Introduction to Random Graphs
• Hamiltonicity thresholds in Achlioptas processes
• Factors in random graphs
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Cuckoo hashing
• Semi‐random graph process
• Optimal threshold for a random graph to be 2-universal
• Creating a Giant Component
• Advances in Cryptology - EUROCRYPT 2004
• The threshold for combs in random graphs
• Explosive Percolation in Random Networks
• Graph colouring and the probabilistic method