66 citations · 457 across the 33 of their papers we have counts for
3 papers · 1 filter
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…