Perfect matchings in o( n log n ) time in regular bipartite graphs

DOI10.1145/1806689.1806697zbMath1293.05291OpenAlexW2145192475MaRDI QIDQ2875130

Ashish Goel, Sanjeev Khanna, Michael Kapralov

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806697

zbMATH Keywords

matchingsgraph algorithmsbipartite regular graphsBirkhoff-von Neumann decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (5)

Finding all maximally-matchable edges in a bipartite graph ⋮ Maximum matching in regular and almost regular graphs ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Spectral Analysis of Matrix Scaling and Operator Scaling ⋮ Unnamed Item

This page was built for publication: Perfect matchings in o( n log n ) time in regular bipartite graphs