research
∙
05/02/2023
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
We study Steiner Forest on H-subgraph-free graphs, that is, graphs that ...
share
research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
08/26/2022
Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs
The Shapley value is the solution concept in cooperative game theory tha...
research
∙
08/26/2022
The Parameterized Complexity Binary CSP for Graphs with a Small Vertex Cover and Related Results
In this paper, we show that Binary CSP with the size of a vertex cover a...
research
∙
06/23/2022
On the parameterized complexity of computing tree-partitions
We study the parameterized complexity of computing the tree-partition-wi...
research
∙
06/23/2022
On the Complexity of Problems on Tree-structured Graphs
In this paper, we introduce a new class of parameterized problems, which...
research
∙
06/20/2022
List Colouring Trees in Logarithmic Space
We show that List Colouring can be solved on n-vertex trees by a determi...
research
∙
02/14/2022
Problems hard for treewidth but easy for stable gonality
We show that some natural problems that are XNLP-hard (which implies W[t...
research
∙
01/31/2022
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
In this paper, we show several parameterized problems to be complete for...
research
∙
06/30/2021
Parameterized Complexities of Dominating and Independent Set Reconfiguration
We settle the parameterized complexities of several variants of independ...
research
∙
05/31/2021
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Let XNLP be the class of parameterized problems such that an instance of...
research
∙
12/02/2020
Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation
In this paper, we show that Bandwidth is hard for the complexity class W...
research
∙
07/17/2020
Parameterized Complexity of Scheduling Chains of Jobs with Delays
In this paper, we consider the parameterized complexity of the following...
research
∙
07/08/2020
Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes
For a graph class 𝒞, the 𝒞-Edge-Deletion problem asks for a given graph ...
research
∙
05/12/2020
Constructing Tree Decompositions of Graphs with Bounded Gonality
In this paper, we give a constructive proof of the fact that the treewid...
research
∙
02/25/2020
Hedonic Seat Arrangement Problems
In this paper, we study a variant of hedonic games, called Seat Arrangem...
research
∙
05/25/2019
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
We study Subgraph Isomorphism on graph classes defined by a fixed forbid...
research
∙
05/09/2019
Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs
In this paper, we show that the Cutwidth, Modified Cutwidth, and Vertex ...
research
∙
05/01/2019
Parameterized Complexity of Conflict-free Graph Coloring
Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-...
research
∙
04/05/2019
Knot Diagrams of Treewidth Two
In this paper, we study knot diagrams for which the underlying graph has...
research
∙
08/21/2018
Stable divisorial gonality is in NP
Divisorial gonality and stable divisorial gonality are graph parameters,...
research
∙
07/31/2018
On Exploring Temporal Graphs of Small Pathwidth
We show that the Temporal Graph Exploration Problem is NP-complete, even...
research
∙
07/18/2018
An ETH-Tight Exact Algorithm for Euclidean TSP
We study exact algorithms for Euclidean TSP in R^d. In the early 1990s ...
research
∙
06/05/2018
Fast Dynamic Programming on Graph Decompositions
In this paper, we consider tree decompositions, branch decompositions, a...
research
∙
03/28/2018
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
03/28/2018
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
02/07/2018
Optimal data structures for stochastic driven simulations
Simulations where we have some prior information on the probability dist...
research
∙
01/10/2013
Pre-processing for Triangulation of Probabilistic Networks
The currently most efficient algorithm for inference with a probabilisti...
research
∙
07/11/2012