Maximum weight bipartite matching in matrix multiplication time
From MaRDI portal
Publication:1035683
DOI10.1016/j.tcs.2009.07.028zbMath1228.05238MaRDI QIDQ1035683
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
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
Fair matchings and related problems, 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, Linear-Time Approximation for Maximum Weight Matching
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