Rank-maximal matchings -- structure and algorithms

DOI10.1016/j.tcs.2018.09.033zbMath1418.91389arXiv1409.4977OpenAlexW2894809631WikidataQ62045775 ScholiaQ62045775MaRDI QIDQ1733053

Meghana Nasre, Prajakta Nimbhorkar, Pratik Ghosal

Publication date: 26 March 2019

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.4977

zbMATH Keywords

algorithmalgorithmsmatchingsone-sided preferencesrank-maximalityrank-maximal matchings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Matching models (91B68)

Related Items (2)

Dynamic rank-maximal and popular matchings ⋮ The dynamics of rank-maximal and popular matchings

Cites Work

• Unnamed Item
• Fair matchings and related problems
• Popular matchings: structure and algorithms
• Optimal popular matchings
• Approximating the permanent of graphs with large factors
• Residence exchange wanted: A stable residence exchange problem
• Manipulation strategies for the rank-maximal matching problem
• Popular Matchings: Structure and Strategic Issues
• Rank-maximal matchings
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Popular Matchings
• Capacitated Rank-Maximal Matchings
• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
• Algorithms and Computation

This page was built for publication: Rank-maximal matchings -- structure and algorithms