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
∙
07/03/2023
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
We prove the following result about approximating the maximum independen...
research
∙
05/03/2023
Approximate Evaluation of Quantitative Second Order Queries
Courcelle's theorem and its adaptations to cliquewidth have shaped the f...
research
∙
10/13/2022
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
The generic homomorphism problem, which asks whether an input graph G ad...
research
∙
04/11/2022
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Temporal graphs naturally model graphs whose underlying topology changes...
research
∙
02/28/2022
Parameterised Partially-Predrawn Crossing Number
Inspired by the increasingly popular research on extending partial graph...
research
∙
02/18/2022
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Hedonic diversity games are a variant of the classical Hedonic games des...
research
∙
09/28/2021
A Unifying Framework for Characterizing and Computing Width Measures
Algorithms for computing or approximating optimal decompositions for dec...
research
∙
12/14/2020
Crossing-Optimal Extension of Simple Drawings
In extension problems of partial graph drawings one is given an incomple...
research
∙
07/08/2020
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
The problem of extending partial geometric graph representations such as...
research
∙
04/25/2020
Extending Partial 1-Planar Drawings
Algorithmic extension problems of partial graph representations such as ...
research
∙
01/27/2020
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
We investigate the following many-to-one stable matching problem with di...
research
∙
08/27/2019