Matching algorithms are fast in sparse random graphs

DOI10.1007/s00224-005-1254-yzbMath1104.68078OpenAlexW2163768829MaRDI QIDQ2432523

Hisao Tamaki, Guido Schäfer, Kurt Mehlhorn, Holger Bast

Publication date: 25 October 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.395.6643

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ Unnamed Item ⋮ Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs ⋮ Approximation algorithms in combinatorial scientific computing

This page was built for publication: Matching algorithms are fast in sparse random graphs