Finding maximum matchings in random regular graphs in linear expected time
From MaRDI portal
Publication:6049997
DOI10.1002/rsa.20980zbMath1522.05462arXiv1808.00825OpenAlexW3108206614MaRDI QIDQ6049997
Alan M. Frieze, Michael Anastos
Publication date: 11 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.00825
Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- The rank of diluted random graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- On tail probabilities for martingales
- Karp–Sipser on Random Graphs with a Fixed Degree Sequence
- Controllability and matchings in random bipartite graphs
- Finding a maximum matching in a sparse random graph in O ( n ) expected time
- Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
- Probability Inequalities for Sums of Bounded Random Variables
This page was built for publication: Finding maximum matchings in random regular graphs in linear expected time
