Efficient algorithms for generalized stable marriage and roommates problems

DOI10.1016/j.tcs.2007.04.029zbMath1190.90159OpenAlexW1994939255WikidataQ57311971 ScholiaQ57311971MaRDI QIDQ995571

David F. Manlove, Tamás Fleiner, Robert W. Irving

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.029

zbMATH Keywords

partial orderstable marriage problemstable roommates problemsuper-stable matchingforbidden pair

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Characterization of super-stable matchings ⋮ Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ The core of housing markets from an agent's perspective: Is it worth sprucing up your home? ⋮ An algorithm for a super-stable roommates problem ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Unnamed Item ⋮ New and simple algorithms for stable flow problems ⋮ Planar Matchings for Weighted Straight Skeletons ⋮ Planar Matchings for Weighted Straight Skeletons ⋮ Stable multi-skill workforce assignments ⋮ Pairwise Preferences in the Stable Marriage Problem ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ The stable marriage problem with ties and restricted edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pairwise kidney exchange
• A new fixed point approach for stable networks and stable marriages
• Preference structures and their numerical representations
• Stable marriage and indifference
• Network flow and 2-satisfiability
• The stable marriage problem with restricted pairs.
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• The structure of stable marriage with indifference
• The set of super-stable marriages forms a distributive lattice
• On a generalization of the stable roommates problem
• The Stable Roommates Problem with Ties
• A necessary and sufficient condition for the existence of a complete stable matching
• Lower Bounds for the Stable Marriage Problem and Its Variants
• NP-complete stable matching problems
• An efficient algorithm for the “stable roommates” problem
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• On the Complexity of Timetable and Multicommodity Flow Problems
• A New Approach to Stable Matching Problems
• College Admissions and the Stability of Marriage

This page was built for publication: Efficient algorithms for generalized stable marriage and roommates problems