Karp-Sipser on random graphs with a fixed degree sequence

DOI10.1017/S0963548311000265MaRDI QIDQ3103622zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tom Bohman, Alan 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

graph drawingKarp-Sipser algorithmrandom graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1139976
• Controllability and matchings in random bipartite graphs
• Finding maximum matchings in random regular graphs in linear expected time
• scientific article; zbMATH DE number 1512672
• Matching algorithms are fast in sparse random graphs

Cites work

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

Cited in

(14)

• The triangle-free process
• The matching process and independent process in random regular graphs and hypergraphs
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• SIR epidemics on random graphs with a fixed degree sequence
• Matchings on infinite graphs
• Understanding the correlation gap for matchings
• The spread of fire on a random multigraph
• Law of large numbers for the SIR epidemic on a random graph with given degrees
• The rank of diluted random graphs
• Singularity of the \(k\)-core of a random graph
• Finding maximum matchings in random regular graphs in linear expected time
• Matching algorithms in the sparse stochastic block model
• The critical Karp-Sipser core of random graphs
• A new impossibility result for online bipartite matching problems

This page was built for publication: Karp-Sipser on random graphs with a fixed degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3103622)