Efficient algorithms for generalized stable marriage and roommates problems

DOI10.1016/J.TCS.2007.04.029MaRDI QIDQ995571zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

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

Recommendations

• An efficient algorithm for the “stable roommates” problem
• Better and simpler approximation algorithms for the stable marriage problem
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• scientific article; zbMATH DE number 45086
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• An approach to robustness in the stable roommates problem and its comparison with the stable marriage problem
• A maximum stable matching for the roommates problem
• Randomized approximation of the stable marriage problem
• Randomized approximation of the stable marriage problem

Cites work

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

Cited in

(18)

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• Characterization of super-stable matchings
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Pairwise Preferences in the Stable Marriage Problem
• scientific article; zbMATH DE number 7561396 (Why is no real title available?)
• Stable matchings with covering constraints: a complete computational trichotomy
• Popular roommates in simply exponential time
• Stable multi-skill workforce assignments
• Planar Matchings for Weighted Straight Skeletons
• The core of housing markets from an agent's perspective: Is it worth sprucing up your home?
• Adapting stable matchings to evolving preferences
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Adapting stable matchings to forced and forbidden pairs
• An efficient algorithm for the “stable roommates” problem
• The stable marriage problem with ties and restricted edges
• An algorithm for a super-stable roommates problem
• Planar matchings for weighted straight skeletons
• Stable marriage and roommates problems with restricted edges: complexity and approximability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995571)