Popular edges and dominant matchings

DOI10.1007/s10107-017-1183-yzbMath1398.05162arXiv1508.00614OpenAlexW2743296665MaRDI QIDQ1800997

Telikepalli Kavitha, Ágnes Cseh

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

matching under preferencespopular matchingdominant matchingpopular edge problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Integer programming (90C10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (19)

Popular Branchings and Their Dual Certificates ⋮ Popular Matchings with Two-Sided Preferences and One-Sided Ties ⋮ Finding popular branchings in vertex-weighted digraphs ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Popularity in the generalized hospital residents setting ⋮ Popular matchings in complete graphs ⋮ Two problems in max-size popular matchings ⋮ Popular critical matchings in the many-to-many setting ⋮ Finding popular branchings in vertex-weighted directed graphs ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Popular matchings with two-sided preference lists and matroid constraints ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Popular matchings: structure and algorithms
• Some remarks on the stable matching problem
• Characterization of stable matchings as extreme points of a polytope
• A new fixed point approach for stable networks and stable marriages
• Network flow and 2-satisfiability
• The stable marriage problem with restricted pairs.
• Popular matchings in the stable marriage problem
• Popular Matchings with Two-Sided Preferences and One-Sided Ties
• Popular Matchings in the Marriage and Roommates Problems
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• College Admissions and the Stability of Marriage

This page was built for publication: Popular edges and dominant matchings