Parameterized complexity and local search approaches for the stable marriage problem with ties
From MaRDI portal
Publication:1959726
DOI10.1007/S00453-009-9326-ZzbMATH Open1204.68148OpenAlexW2000321198MaRDI QIDQ1959726FDOQ1959726
Publication date: 7 October 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9326-z
Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Three Fast Algorithms for Four Problems in Stable Marriage
- College Admissions and the Stability of Marriage
- Stable assignment with couples: parameterized complexity and local search
- On Local Search and Placement of Meters in Networks
- Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- On the Hardness of Losing Weight
- Hard variants of stable marriage.
- Stable marriage and indifference
- Approximability results for stable marriage problems with ties.
- Better and Simpler Approximation Algorithms for the Stable Marriage Problem
- Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
Cited In (20)
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Solving hard stable matching problems involving groups of similar agents
- Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
- Parameterized Dynamic Cluster Editing
- Searching for better fill-in
- Algorithms and complexity of strongly stable non-crossing matchings
- Maximum stable matching with one-sided ties of bounded length
- Stable matching games: manipulation via subgraph isomorphism
- Stable matchings with covering constraints: a complete computational trichotomy
- Parameterized dynamic cluster editing
- Adapting stable matchings to forced and forbidden pairs
- On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)
- Backdoors to Satisfaction
- Local search approaches in stable matching problems
- How hard is it to satisfy (almost) all roommates
- Balanced stable marriage: how close is close enough?
- Stable marriage with groups of similar agents
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Parameterized algorithms for stable matching with ties and incomplete lists
- Sex-equal stable matchings: complexity and exact algorithms
This page was built for publication: Parameterized complexity and local search approaches for the stable marriage problem with ties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1959726)
