Maximum weight bipartite matching in matrix multiplication time

DOI10.1016/j.tcs.2009.07.028zbMath1228.05238MaRDI 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 paths; matrix multiplication; matchings in graphs; weighted perfect matchings

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

Related Items

A simple reduction from maximum weight matching to maximum cardinality matching, A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors, Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation, Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation

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