A scaling algorithm for maximum weight matching in bipartite graphs
From MaRDI portal
Publication:5743486
zbMATH Open1425.05150MaRDI QIDQ5743486FDOQ5743486
Authors: Ran Duan, Hsin-Hao Su 
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095227
Recommendations
- Scaling algorithms for weighted matching in general graphs
- Scaling algorithms for weighted matching in general graphs
- Weighted Bipartite Matching in Matrix Multiplication Time
- Maximum weight bipartite matching in matrix multiplication time
- Faster scaling algorithms for general graph matching problems
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Fibonacci heaps and their uses in improved network optimization algorithms
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Paths, Trees, and Flowers
- On some techniques useful for solution of transportation network problems
- Title not available (Why is that?)
- An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Faster scaling algorithms for general graph matching problems
- Faster Scaling Algorithms for Network Problems
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Matrix multiplication via arithmetic progressions
- New scaling algorithms for the assignment and minimum mean cycle problems
- Algorithms for the Assignment and Transportation Problems
- Algebraic algorithms for matching and matroid problems
- Scaling Algorithms for the Shortest Paths Problem
- A decomposition theorem for partially ordered sets
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Clique partitions, graph compression and speeding-up algorithms
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Algorithms for dense graphs and networks on the random access computer
- A decomposition theorem for maximum weight bipartite matchings
- Equivalence between priority queues and sorting
- Looking for the order of a system of arbitrary ordinary differential equations. Translated from the Latin manuscript by François Ollivier. Edited by S. Cohn and C. W. Borchardt.
- Weighted Bipartite Matching in Matrix Multiplication Time
Cited In (24)
- An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
- A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
- Bipartite matching with linear edge weights
- Fair matchings and related problems
- A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
- Maximum weight bipartite matching in matrix multiplication time
- Traversing combinatorial 0/1-polytopes via optimization
- An addendum on the incremental assignment problem
- Scaling algorithms for weighted matching in general graphs
- A simple reduction from maximum weight matching to maximum cardinality matching
- Finding a complete matching with the maximum product on weighted bipartite graphs
- Experimental and Efficient Algorithms
- Parameterized results on acyclic matchings with implications for related problems
- Data locality and replica aware virtual cluster embeddings
- Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
- Efficient algorithms for maximum weight matchings in general graphs with small edge weights
- A modified decomposition algorithm for maximum weight bipartite matching and its experimental evaluation
- Title not available (Why is that?)
- Scaling algorithms for weighted matching in general graphs
- Weighted Bipartite Matching in Matrix Multiplication Time
- Algorithms for weighted matching generalizations. I: Bipartite graphs, \(b\)-matching, and unweighted \(f\)-factors
- A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
- A combinatorial algorithm for weighted stable sets in bipartite graphs
- EmbAssi: embedding assignment costs for similarity search in large graph databases
Uses Software
This page was built for publication: A scaling algorithm for maximum weight matching in bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743486)
