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 QIDQ2105427
Klaus Heeger, Robert Bredereck, 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
Cites Work
- Unnamed Item
- Unnamed Item
- Stable assignment with couples: parameterized complexity and local search
- The structure of graphs not admitting a fixed immersion
- The stable marriage problem with ties and restricted edges
- Pairwise kidney exchange
- A new fixed point approach for stable networks and stable marriages
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Treewidth. Computations and approximations
- Hard variants of stable marriage.
- The structure of stable marriage with indifference
- An FPT 2-approximation for tree-cut decomposition
- Parameterized algorithms for stable matching with ties and incomplete lists
- The stable roommates problem with short lists
- Stable matching with preferences derived from a psychological model
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Solving hard stable matching problems involving groups of similar agents
- On structural parameterizations of the bounded-degree vertex deletion problem
- Stable matchings with covering constraints: a complete computational trichotomy
- Tight lower bounds for certain parameterized NP-hard problems
- A fine-grained view on stable many-to-one matching problems with lower and upper quotas
- Multidimensional stable roommates with master list
- New Races in Parameterized Algorithmics
- On a generalization of the stable roommates problem
- Algorithmic Applications of Tree-Cut Width
- NP-complete stable matching problems
- A 3/2-Approximation Algorithm for General Stable Marriage
- An efficient algorithm for the “stable roommates” problem
- Immersions in Highly Edge Connected Graphs
- How hard is it to satisfy (almost) all roommates
- On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- Bribery and Control in Stable Marriage
- SAT-Encodings for Treecut Width and Treedepth
- Algorithmics of Matching Under Preferences
- Parameterized Algorithms
- Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
- College Admissions and the Stability of Marriage
- Balanced stable marriage: how close is close enough?
- On the complexity of \(k\)-SAT
This page was built for publication: Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
