Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
DOI10.1002/RSA.20963zbMATH Open1497.68365OpenAlexW3090469133MaRDI QIDQ3386520FDOQ3386520
Authors: Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich 
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
Recommendations
- Very fast construction of bounded-degree spanning graphs via the semi-random graph process
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Fast uniform generation of random graphs with given degree sequences
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Fast constructions of light-weight spanners for general graphs
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Publication:4942233
- Fast constructions of lightweight spanners for general graphs
- Fully dynamic randomized algorithms for graph spanners
- Embedding spanning bounded degree subgraphs in randomly perturbed graphs
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)
Cites Work
- Title not available (Why is that?)
- Spanning trees in random graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Advances in Cryptology - EUROCRYPT 2004
- Factors in random graphs
- Avoiding small subgraphs in Achlioptas processes
- Balanced Allocations
- Cuckoo hashing
- Small subgraphs in random graphs and the power of multiple choices
- Graph colouring and the probabilistic method
- Introduction to Random Graphs
- Explosive percolation in random networks
- Hamilton connected graphs
- Avoiding a giant component
- Achlioptas process phase transitions are continuous
- Creating a Giant Component
- Birth control for giants
- The Bohman-Frieze process near criticality
- Hamiltonicity thresholds in Achlioptas processes
- A geometric Achlioptas process
- Optimal threshold for a random graph to be 2-universal
- The threshold for combs in random graphs
- Semi-random graph process
Cited In (6)
- Semi-random graph process
- Perfect matchings in the semirandom graph process
- Semi-random process without replacement
- Sharp thresholds in adaptive random graph processes
- \(d\)-connectivity of the random graph with restricted budget
- Very fast construction of bounded-degree spanning graphs via the semi-random graph process
This page was built for publication: Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386520)
