Karp–Sipser on Random Graphs with a Fixed Degree Sequence

DOI10.1017/S0963548311000265zbMath1234.05205OpenAlexW2144797269WikidataQ57401450 ScholiaQ57401450MaRDI QIDQ3103622

Tom Bohman, Alan M. Frieze

Publication date: 8 December 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548311000265

zbMATH Keywords

random graphgraph drawingKarp-Sipser algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

SIR epidemics on random graphs with a fixed degree sequence ⋮ Matchings on infinite graphs ⋮ Singularity of the \(k\)-core of a random graph ⋮ Finding maximum matchings in random regular graphs in linear expected time ⋮ The rank of diluted random graphs ⋮ The spread of fire on a random multigraph ⋮ The triangle-free process ⋮ Unnamed Item ⋮ Weighted enumeration of spanning subgraphs in locally tree-like graphs ⋮ Law of large numbers for the SIR epidemic on a random graph with given degrees ⋮ The matching process and independent process in random regular graphs and hypergraphs

Cites Work

• Unnamed Item
• Maximum matchings in a class of random graphs
• Matchings in random regular bipartite digraphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
• Perfect matchings in random bipartite graphs with minimal degree at least 2
• A critical point for random graphs with a given degree sequence
• Colouring Random 4-Regular Graphs
• Paths, Trees, and Flowers
• Spectra of random graphs with given expected degrees
• On the existence of a factor of degree one of a connected random graph

This page was built for publication: Karp–Sipser on Random Graphs with a Fixed Degree Sequence