A Size-Popularity Tradeoff in the Stable Marriage Problem

DOI10.1137/120902562zbMath1310.68273OpenAlexW2063222520MaRDI QIDQ5419029

Telikepalli Kavitha

Publication date: 4 June 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120902562

zbMATH Keywords

bipartite graphsmatchingspreference lists

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (17)

Popular Branchings and Their Dual Certificates ⋮ Popular Matchings with Two-Sided Preferences and One-Sided Ties ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Popularity in the generalized hospital residents setting ⋮ Popular matchings in complete graphs ⋮ Finding and Recognizing Popular Coalition Structures ⋮ Two problems in max-size popular matchings ⋮ Popular critical matchings in the many-to-many setting ⋮ Popular matchings with two-sided preference lists and matroid constraints ⋮ Popular edges and dominant matchings ⋮ Popular Matchings in Complete Graphs ⋮ Unnamed Item ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Popular Matchings with Lower Quotas ⋮ How Good Are Popular Matchings ⋮ Understanding Popular Matchings via Stable Matchings ⋮ Popular branchings and their dual certificates

This page was built for publication: A Size-Popularity Tradeoff in the Stable Marriage Problem