Popular Matchings and Limits to Tractability

DOI10.1137/1.9781611975482.173zbMath1432.68162arXiv1805.11473OpenAlexW2806692490MaRDI QIDQ5236364

XingYu Zhang, Vladlena Powers, Yuri Faenza, Telikepalli Kavitha

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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) Matching models (91B68)

Related Items (12)

Popular Branchings and Their Dual Certificates ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Popular matchings in complete graphs ⋮ Finding and Recognizing Popular Coalition Structures ⋮ Two problems in max-size popular matchings ⋮ On weakly and strongly popular rankings ⋮ Finding popular branchings in vertex-weighted directed graphs ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Unpopularity factor in the marriage and roommates problems ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Understanding Popular Matchings via Stable Matchings ⋮ Popular branchings and their dual certificates

This page was built for publication: Popular Matchings and Limits to Tractability