Maximum weight bipartite matching in matrix multiplication time
DOI10.1016/J.TCS.2009.07.028zbMATH Open1228.05238OpenAlexW1999848117MaRDI QIDQ1035683FDOQ1035683
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- On a routing problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Scaling algorithms for network problems
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Faster Scaling Algorithms for Network Problems
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- Algorithms for the Assignment and Transportation Problems
- Scaling Algorithms for the Shortest Paths Problem
- Algorithms – ESA 2005
- Constructing a perfect matching is in random NC
- Matching is as easy as matrix inversion
- High-order lifting and integrality certification
- Maximum matchings in general graphs through randomization
- A decomposition theorem for maximum weight bipartite matchings
- Title not available (Why is that?)
Cited In (30)
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fair matchings and related problems
- A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
- 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
- A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
- Perturbation analysis of maximum-weighted bipartite matchings with low rank data
- Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
- Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages
- Title not available (Why is that?)
- Linear-time approximation for maximum weight matching
- A simple reduction from maximum weight matching to maximum cardinality matching
- A scaling algorithm for maximum weight matching in bipartite graphs
- Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
- Fine-tuning decomposition theorem for maximum weight bipartite matching
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Experimental and Efficient Algorithms
- Algebraic Graph Algorithms
- Efficient algorithms for maximum weight matchings in general graphs with small edge weights
- Algebraic algorithms for fractional linear matroid parity via noncommutative rank
- Title not available (Why is that?)
- Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
- Weighted Bipartite Matching in Matrix Multiplication Time
- Exact and approximation algorithms for weighted matroid intersection
- Algorithms for weighted matching generalizations. I: Bipartite graphs, \(b\)-matching, and unweighted \(f\)-factors
- Maximum bipartite matchings with low rank data: locality and perturbation analysis
- Multiplicative auction algorithm for approximate maximum weight bipartite matching
This page was built for publication: Maximum weight bipartite matching in matrix multiplication time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1035683)
