Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
From MaRDI portal
Publication:2105427
DOI10.1016/J.IC.2022.104943OpenAlexW2990125763MaRDI QIDQ2105427FDOQ2105427
Authors: Robert Bredereck, Klaus Heeger, Dušan Knop, Rolf Niedermeier 
Publication date: 8 December 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.09379
Recommendations
- Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
- Parameterized algorithms for stable matching with ties and incomplete lists
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- How hard is it to satisfy (almost) all roommates?
- Parameterized complexity and local search approaches for the stable marriage problem with ties
Cites Work
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- NP-complete stable matching problems
- Title not available (Why is that?)
- Parameterized algorithms
- College Admissions and the Stability of Marriage
- On the complexity of \(k\)-SAT
- Treewidth. Computations and approximations
- New races in parameterized algorithmics
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- Stable assignment with couples: parameterized complexity and local search
- The structure of graphs not admitting a fixed immersion
- Title not available (Why is that?)
- Immersions in highly edge connected graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Multidimensional stable roommates with master list
- An efficient algorithm for the “stable roommates” problem
- Pairwise kidney exchange
- Hard variants of stable marriage.
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Stable matching with preferences derived from a psychological model
- The structure of stable marriage with indifference
- A 3/2-Approximation Algorithm for General Stable Marriage
- A new fixed point approach for stable networks and stable marriages
- Stable matchings with covering constraints: a complete computational trichotomy
- On a generalization of the stable roommates problem
- The stable marriage problem with ties and restricted edges
- Algorithmic applications of tree-cut width
- Parameterized algorithms for stable matching with ties and incomplete lists
- The stable roommates problem with short lists
- How hard is it to satisfy (almost) all roommates?
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- On structural parameterizations of the bounded-degree vertex deletion problem
- Solving hard stable matching problems involving groups of similar agents
- A fine-grained view on stable many-to-one matching problems with lower and upper quotas
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Bribery and control in stable marriage
- SAT-encodings for treecut width and treedepth
- Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
- Balanced stable marriage: how close is close enough?
Cited In (1)
This page was built for publication: Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105427)
