Matching algorithms are fast in sparse random graphs
From MaRDI portal
Publication:2432523
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
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
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
