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-hardNP-completepolynomial transformationideal weightsex-equal stable marriage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05)

Related Items (10)

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

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

This page was built for publication: Complexity of the sex-equal stable marriage problem