research
∙
07/11/2023
Maximizing Social Welfare in Score-Based Social Distance Games
Social distance games have been extensively studied as a coalition forma...
share
research
∙
05/17/2023
Optimal Seat Arrangement: What Are the Hard and Easy Cases?
We study four NP-hard optimal seat arrangement problems [Bodlaender et a...
research
∙
12/12/2022
Degreewidth: a New Parameter for Solving Problems on Tournaments
In the paper, we define a new parameter for tournaments called degreewid...
research
∙
03/17/2022
Cores in Friend-Oriented Hedonic Games: Verification is Surprisingly Harder than Searching
We resolve an open question by Woeginger [Open Problem 13, SOFSEM '13] r...
research
∙
02/24/2022
Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], ...
research
∙
08/09/2021
Euclidean 3D Stable Roommates is NP-hard
We establish NP-completeness for the Euclidean 3D Stable Roommates probl...
research
∙
02/19/2021
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Partitioning a region into districts to favor a particular candidate or ...
research
∙
11/24/2020
Fractional Matchings under Preferences: Stability and Optimality
We thoroughly study a generalized version of the classic Stable Marriage...
research
∙
05/17/2020