Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication

DOI10.1016/0020-0190(81)90142-3zbMath0469.68052OpenAlexW1993675745MaRDI QIDQ1157169

Shlomo Moran, Oscar H. Ibarra

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90142-3

zbMATH Keywords

bipartite graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (4)

Linear-Time Approximation for Maximum Weight Matching ⋮ Some independence results in complexity theory^† ⋮ Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages ⋮ Path factors and parallel knock-out schemes of almost claw-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Shortest-path problem is not harder than matrix multiplication
• New combinations of methods for the acceleration of matrix multiplication
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication