research
∙
02/22/2023
Fair Correlation Clustering in Forests
The study of algorithmic fairness received growing attention recently. T...
share
research
∙
07/19/2022
Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
In the 1970s, Győri and Lovász showed that for a k-connected n-vertex gr...
research
∙
12/06/2021
Fixed-Parameter Sensitivity Oracles
We combine ideas from distance sensitivity oracles (DSOs) and fixed-para...
research
∙
07/28/2021
Dense Graph Partitioning on sparse and dense graphs
We consider the problem of partitioning a graph into a non-fixed number ...
research
∙
07/10/2021
Connected k-partition of k-connected graphs and c-claw-free graphs
A connected partition is a partition of the vertices of a graph into set...
research
∙
01/06/2021
Fine-Grained Complexity of Regular Path Queries
A regular path query (RPQ) is a regular expression q that returns all no...
research
∙
11/09/2020
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
We study the problem of counting the number of homomorphisms from an inp...
research
∙
11/09/2020
Balanced Crown Decomposition for Connectivity Constraints
We introduce the balanced crown decomposition that captures the structur...
research
∙
05/14/2020
Shortest Distances as Enumeration Problem
We investigate the single source shortest distance (SSSD) and all pairs ...
research
∙
02/04/2020
The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
Several important optimization problems in the area of vehicle routing c...
research
∙
11/06/2019
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization
We generalize the tree doubling and Christofides algorithm, the two most...
research
∙
05/08/2019
Zeros and approximations of Holant polynomials on the complex plane
We present fully polynomial approximation schemes for general classes of...
research
∙
02/28/2019
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
We investigate the locality number, a recently introduced structural par...
research
∙
10/10/2018
Extension of vertex cover and independent set in some classes of graphs and generalizations
We consider extension variants of the classical graph problems Vertex Co...
research
∙
10/10/2018
On the Complexity of Solution Extension of Optimization Problems
The question if a given partial solution to a problem can be extended re...
research
∙
06/19/2017