8 citations · 8 across the 2 of their papers we have counts for
7 papers
The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
Vsevolod A. Afanasev, René van Bevern, Oxana Yu. Tsidulko
The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We…
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
René van Bevern, Viktoriia A. Slugina
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by…
Optimal-size problem kernels for -Hitting Set in linear time and space
René van Bevern, Pavel V. Smirnov
The known linear-time kernelizations for -Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting ri…
On approximate data reduction for the Rural Postman Problem: Theory and experiments
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given an undirected graph with edge weights and a subset of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of…
Parameterized algorithms and data reduction for the short secluded --path problem
René van Bevern, Till Fluschnik, Oxana Yu. Tsidulko
Given a graph , two vertices , and two integers , the Short Secluded Path problem is to find a simple --path with at most vertices and n…
Precedence-constrained scheduling problems parameterized by partial order width
René van Bevern, Robert Bredereck, Laurent Bulteau +3
Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,|, the problem of finding a non-preempti…