Hardness results for stable exchange problems

DOI10.1016/j.tcs.2017.01.023zbMath1359.68111OpenAlexW2588380045MaRDI QIDQ5965780

Zsuzsa Mészáros-Karkus

Publication date: 16 March 2017

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

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

zbMATH Keywords

computational complexitykidney exchangestable exchangestable partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (2)

Randomized parameterized algorithms for the kidney exchange problem ⋮ Novel integer programming models for the stable kidney exchange problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the parameterized complexity of multiple-interval graph problems
• Weak versus strong domination in a market with indivisible goods
• Stable matchings in three-sided systems with cyclic preferences
• On cores and indivisibility
• The kidney exchange problem: how hard is it to find a donor?
• Three-sided stable matchings with cyclic preferences
• The cycle roommates problem: a hard case of kidney exchange
• The Stable Roommates Problem with Ties
• Kidney Exchange
• A necessary and sufficient condition for the existence of a complete stable matching
• Three-Dimensional Stabl Matching Problems
• An efficient algorithm for the “stable roommates” problem
• MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS
• Three-dimensional stable matching with cyclic preferences
• College Admissions and the Stability of Marriage

This page was built for publication: Hardness results for stable exchange problems