
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
The NPhard Multiple Hitting Set problem is finding a minimumcardinalit...
read it

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...
read it

A historical note on the 3/2approximation algorithm for the metric traveling salesman problem
One of the most fundamental results in combinatorial optimization is the...
read it

Optimalsize problem kernels for dHitting Set in linear time and space
We improve two lineartime data reduction algorithms for the dHitting S...
read it

PolynomialTime Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomialtime prepocessing...
read it

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 ...
read it

Fixedparameter algorithms for maximumprofit facility location under matroid constraints
We consider a variant of the matroid median problem introduced by Krishn...
read it

Fixedparameter algorithms for facility location under matroid constraints
We introduce a new uncapacitated discrete facility location problem, whe...
read it

Facility location under matroid constraints: fixedparameter algorithms and applications
We study an NPhard uncapacitated discrete facility location problem: Th...
read it

Parameterized algorithms and data reduction for the short secluded stpath problem
Given a graph G=(V,E), two vertices s,t∈ V, and two integers k,ℓ, we sea...
read it

Parameterized algorithms and data reduction for safe convoy routing
We study a problem that models safely routing a convoy through a transpo...
read it

(Wireless) Scheduling, Graph Classes, and cColorable Subgraphs
Inductive kindependent graphs are a generalization of chordal graphs an...
read it

Parameterized complexity of machine scheduling: 15 open problems
Machine scheduling problems are a longtime key domain of algorithms and...
read it
René van Bevern
is this you? claim profile