Complexity of the sex-equal stable marriage problem

DOI10.1007/BF03167200zbMath0782.68060MaRDI QIDQ689901

Akiko Kato

Publication date: 13 March 1994

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hard; NP-complete; polynomial transformation; ideal weight; sex-equal stable marriage

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

05A05: Permutations, words, matrices

Related Items

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Balanced stable marriage: how close is close enough?, Computing relaxations for the three-dimensional stable matching problem with cyclic preferences, Sex-equal stable matchings: complexity and exact algorithms, Approximability results for stable marriage problems with ties., A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences, Constrained stable marriage with free edges or few blocking pairs, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Stable fractional matchings, Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Every finite distributive lattice is a set of stable matchings
• Linear programming brings marital bliss
• Characterization of stable matchings as extreme points of a polytope
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• College Admissions and the Stability of Marriage