research
∙
07/18/2022
A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
The NP-hard graphical traveling salesman problem (GTSP) is to find a clo...
share
research
∙
05/18/2022
On data reduction for dynamic vector bin packing
We study a dynamic vector bin packing (DVBP) problem. We show hardness f...
research
∙
09/13/2021
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinalit...
research
∙
11/08/2020
The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
The Hierarchical Chinese Postman Problem is finding a shortest traversal...
research
∙
04/06/2020
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
One of the most fundamental results in combinatorial optimization is the...
research
∙
03/10/2020
Optimal-size problem kernels for d-Hitting Set in linear time and space
We improve two linear-time data reduction algorithms for the d-Hitting S...
research
∙
10/01/2019
Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomial-time prepocessing...
research
∙
12/25/2018
On (1+ε)-approximate problem kernels for the Rural Postman Problem
Given a graph G=(V,E) with edge weights ω E→ N∪{0} and a subset R⊆ E of ...
research
∙
06/29/2018
Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
We consider a variant of the matroid median problem introduced by Krishn...
research
∙
06/29/2018
Fixed-parameter algorithms for facility location under matroid constraints
We introduce a new uncapacitated discrete facility location problem, whe...
research
∙
06/29/2018
Facility location under matroid constraints: fixed-parameter algorithms and applications
We study an NP-hard uncapacitated discrete facility location problem: Th...
research
∙
06/25/2018
Parameterized algorithms and data reduction for the short secluded s-t-path problem
Given a graph G=(V,E), two vertices s,t∈ V, and two integers k,ℓ, we sea...
research
∙
06/25/2018
Parameterized algorithms and data reduction for safe convoy routing
We study a problem that models safely routing a convoy through a transpo...
research
∙
12/18/2017
(Wireless) Scheduling, Graph Classes, and c-Colorable Subgraphs
Inductive k-independent graphs are a generalization of chordal graphs an...
research
∙
09/06/2017
