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

DOI10.1002/RSA.20963MaRDI QIDQ3386520zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A geometric Achlioptas process
• Achlioptas process phase transitions are continuous
• Advances in Cryptology - EUROCRYPT 2004
• Avoiding a giant component
• Avoiding small subgraphs in Achlioptas processes
• Balanced Allocations
• Birth control for giants
• Creating a Giant Component
• Cuckoo hashing
• Explosive percolation in random networks
• Factors in random graphs
• Graph colouring and the probabilistic method
• Hamilton connected graphs
• Hamiltonicity thresholds in Achlioptas processes
• Introduction to Random Graphs
• Optimal threshold for a random graph to be 2-universal
• Semi-random graph process
• Small subgraphs in random graphs and the power of multiple choices
• Spanning trees in random graphs
• The Bohman-Frieze process near criticality
• The threshold for combs in random graphs

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)