Popular matchings in the stable marriage problem

DOI10.1016/j.ic.2012.10.012zbMath1266.05120OpenAlexW2037078275MaRDI QIDQ1951580

Chien-Chung Huang, Telikepalli Kavitha

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.012

zbMATH Keywords

stable marriage problemmaximum cardinality popular matchingstrict preferences. incomplete lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Popular Branchings and Their Dual Certificates ⋮ A social choice approach to ordinal group activity selection ⋮ Popular Matchings with Two-Sided Preferences and One-Sided Ties ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Popular matchings in complete graphs ⋮ The Generalized Popular Condensation Problem ⋮ Two problems in max-size popular matchings ⋮ Popular critical matchings in the many-to-many setting ⋮ Finding popular branchings in vertex-weighted directed graphs ⋮ Application of pair approximation method to modeling and analysis of a marriage network ⋮ PROM: efficient matching query processing on high-dimensional data ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Popular matchings with two-sided preference lists and matroid constraints ⋮ Popular edges and dominant matchings ⋮ (Un)stable matchings with blocking costs ⋮ Unnamed Item ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Popular Matchings with Lower Quotas ⋮ Understanding Popular Matchings via Stable Matchings ⋮ Popular branchings and their dual certificates