research
∙
08/22/2023
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Recently, Brand, Ganian and Simonov introduced a parameterized refinemen...
share
research
∙
08/21/2023
Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
In a right-angle crossing (RAC) drawing of a graph, each edge is represe...
research
∙
07/11/2023
Maximizing Social Welfare in Score-Based Social Distance Games
Social distance games have been extensively studied as a coalition forma...
research
∙
07/03/2023
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most f...
research
∙
05/03/2023
Approximate Evaluation of Quantitative Second Order Queries
Courcelle's theorem and its adaptations to cliquewidth have shaped the f...
research
∙
04/27/2023
A Parameterized Theory of PAC Learning
Probably Approximately Correct (i.e., PAC) learning is a core concept of...
research
∙
04/27/2023
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
The QSAT problem, which asks to evaluate a quantified Boolean formula (Q...
research
∙
02/20/2023
Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
The task of finding an extension to a given partial drawing of a graph w...
research
∙
10/13/2022
Threshold Treewidth and Hypertree Width
Treewidth and hypertree width have proven to be highly successful struct...
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
∙
08/26/2022
Testing Upward Planarity of Partial 2-Trees
We present an O(n^2)-time algorithm to test whether an n-vertex directed...
research
∙
06/30/2022
Bounding and computing obstacle numbers of graphs
An obstacle representation of a graph G consists of a set of pairwise di...
research
∙
06/30/2022
Slim Tree-Cut Width
Tree-cut width is a parameter that has been introduced as an attempt to ...
research
∙
06/03/2022
Weighted Model Counting with Twin-Width
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and ...
research
∙
06/01/2022
Algorithmic Applications of Tree-Cut Width
The recently introduced graph parameter tree-cut width plays a similar r...
research
∙
03/10/2022
Parameterized Algorithms for Upward Planarity
We obtain new parameterized algorithms for the classical problem of dete...
research
∙
02/28/2022
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Decompositional parameters such as treewidth are commonly used to obtain...
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
∙
09/09/2021
Worbel: Aggregating Point Labels into Word Clouds
Point feature labeling is a classical problem in cartography and GIS tha...
research
∙
06/18/2021
Graphs with at most two moplexes
A moplex is a natural graph structure that arises when lifting Dirac's c...
research
∙
12/14/2020
Crossing-Optimal Extension of Simple Drawings
In extension problems of partial graph drawings one is given an incomple...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
research
∙
08/19/2020
Parameterized Algorithms for Queue Layouts
An h-queue layout of a graph G consists of a linear order of its vertice...
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
∙
11/29/2019
SAT-Encodings for Treecut Width and Treedepth
In this paper we propose, implement, and test the first practical decomp...
research
∙
11/04/2019
On Clustering Incomplete Data
We study fundamental clustering problems for incomplete data. In this se...
research
∙
08/27/2019
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
We develop a framework for applying treewidth-based dynamic programming ...
research
∙
08/23/2019
Parameterized Algorithms for Book Embedding Problems
A k-page book embedding of a graph G draws the vertices of G on a line a...
research
∙
08/14/2019
On Strict (Outer-)Confluent Graphs
A strict confluent (SC) graph drawing is a drawing of a graph with verti...
research
∙
07/29/2019
A Join-Based Hybrid Parameter for Constraint Satisfaction
We propose joinwidth, a new complexity parameter for the Constraint Sati...
research
∙
09/03/2018
The Complexity Landscape of Decompositional Parameters for ILP
Integer Linear Programming (ILP) can be seen as the archetypical problem...
research
∙
08/21/2018
Group Activity Selection with Few Agent Types
The Group Activity Selection Problem (GASP) models situations where a gr...
research
∙
08/10/2018
The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
This paper revisits the classical Edge Disjoint Paths (EDP) problem, whe...
research
∙
04/10/2018
Parameterized Algorithms for the Matrix Completion Problem
We consider two matrix completion problems, in which we are given a matr...
research
∙
11/06/2017
Small Resolution Proofs for QBF using Dependency Treewidth
In spite of the close connection between the evaluation of quantified Bo...
research
∙
11/06/2017