A Fast Perfect-Matching Algorithm in Random Graphs

DOI10.1137/0403006zbMath0733.05072OpenAlexW1971612468MaRDI QIDQ3360222

Olivier Goldschmidt, Dorit S. Hochbaum

Publication date: 1990

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0403006

zbMATH Keywords

random graphsperfect matchinggreedy matching algorithm

Mathematics Subject Classification ID

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

Related Items (1)

Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

This page was built for publication: A Fast Perfect-Matching Algorithm in Random Graphs