Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

DOI10.4230/LIPIcs.ISAAC.2019.44OpenAlexW2991419203MaRDI QIDQ5875607

Dušan Knop, Rolf Niedermeier, Klaus Heeger, Robert Bredereck

Publication date: 3 February 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.44

zbMATH Keywords

treewidthstable matchingfixed-parameter tractabilityW[1-hardness]tree-cut widthtreedepthacceptability graphfeedback set numbers

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts, Algorithmic Applications of Tree-Cut Width, Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters