Sex-equal stable matchings: complexity and exact algorithms

DOI10.1007/s00453-012-9672-0zbMath1360.68515OpenAlexW2046229127MaRDI QIDQ528851

Robert W. Irving, Eric J. McDermid

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9672-0

zbMATH Keywords

dynamic programmingseries-parallel graphsexact algorithmsinduced planar subgraphsXP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Graph algorithms (graph-theoretic aspects) (05C85) Matching models (91B68)

Related Items (7)

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ 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 ⋮ Solving stable matching problems using answer set programming ⋮ Balanced stable marriage: how close is close enough? ⋮ Three-sided matching problem with mixed preferences ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stable assignment with couples: parameterized complexity and local search
• Complexity of the sex-equal stable marriage problem
• Some remarks on the stable matching problem
• Understanding the generalized median stable matchings
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Planarization and fragmentability of some classes of graphs
• Open problems around exact algorithms
• The Geometry of Fractional Stable Matchings and Its Applications
• Approximation algorithms for the sex-equal stable marriage problem
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• The Recognition of Series Parallel Digraphs
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Stable networks and product graphs
• Finding a Level Ideal of a Poset
• College Admissions and the Stability of Marriage

This page was built for publication: Sex-equal stable matchings: complexity and exact algorithms