Maximum weight bipartite matching in matrix multiplication time

DOI10.1016/j.tcs.2009.07.028zbMath1228.05238OpenAlexW1999848117MaRDI QIDQ1035683

Piotr Sankowski

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.028

zbMATH Keywords

shortest pathsmatrix multiplicationmatchings in graphsweighted perfect matchings

Mathematics Subject Classification ID

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) Randomized algorithms (68W20)

Related Items (13)

Fair matchings and related problems ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages ⋮ Unnamed Item ⋮ Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation ⋮ A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Scaling algorithms for network problems
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• High-order lifting and integrality certification
• A Decomposition Theorem for Maximum Weight Bipartite Matchings
• Maximum matchings in general graphs through randomization
• On a routing problem
• Algorithms for the Assignment and Transportation Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Faster Scaling Algorithms for Network Problems
• Scaling Algorithms for the Shortest Paths Problem
• Algorithms – ESA 2005

This page was built for publication: Maximum weight bipartite matching in matrix multiplication time