Reducing rank-maximal to maximum weight matching

DOI10.1016/J.TCS.2007.08.004MaRDI QIDQ2465632zbMATH OpenOpenAlexFDO

Authors Dimitrios Michail

Publication date 7 January 2008

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

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

zbMATH Keywords

bipartite graphmatchingpreference listsrank-maximalweighted matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• Rank-maximal matchings
• scientific article; zbMATH DE number 6469133

Cites work

• A decomposition theorem for maximum weight bipartite matchings
• Algorithms and Computation
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An efficient cost scaling algorithm for the assignment problem
• Faster Scaling Algorithms for Network Problems
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 6469133 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• On a conjecture by Gale about one-sided matching problems
• Popular matchings
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Weak versus strong domination in a market with indivisible goods

Cited in

(12)

• Donation center location problem
• Approximation by lexicographically maximal solutions in matching and matroid intersection problems
• Pareto optimality in coalition formation
• Fair matchings and related problems
• Fair matchings and related problems
• Graded Matching for Large Observational Studies
• Pareto stable matchings under one-sided matroid constraints
• A new approach to the Pareto stable matching problem
• Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• Maximum bipartite matchings with low rank data: locality and perturbation analysis
• Abundant neighborhoods, two-sided markets, and maximal matchings

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Reducing rank-maximal to maximum weight matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465632)