66 citations · 457 across the 33 of their papers we have counts for
34 papers
Concurrent Splay-Based Tree
Vitaly Aksenov, Rene van Bevern, Artem Shilkin
Most work on efficient concurrent ordered indices, such as concurrent binary search trees, B-trees, skip lists, etc., has focused on data structures that provide good \emph{worst-c…
A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
René van Bevern, Daniel A. Skachkov
The NP-hard graphical traveling salesman problem (GTSP) is to find a closed walk of total minimum weight that visits each vertex in an undirected edge-weighted and not necessarily…
On data reduction for dynamic vector bin packing
René van Bevern, Andrey Melnikov, Pavel Smirnov +1
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal nu…
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
René van Bevern, Artem M. Kirilin, Daniel A. Skachkov +2
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well…
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…
Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
Matthias Bentert, René van Bevern, Till Fluschnik +2
Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduc…
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…
Representative families for matroid intersections, with applications to location, packing, and covering problems
René van Bevern, Oxana Yu. Tsidulko, Philipp Zschoche
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location p…
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…
Inductive -independent graphs and -colorable subgraphs in scheduling: A review
Matthias Bentert, René van Bevern, Rolf Niedermeier
Inductive -independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard p…
Parameterized complexity of machine scheduling: 15 open problems
Matthias Mnich, René van Bevern
Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To sti…
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Matthias Bentert, René van Bevern, André Nichterlein +2
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted -vertex graph, fin…
Fixed-Parameter Algorithms for DAG Partitioning
René van Bevern, Robert Bredereck, Morgan Chopin +4
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic…
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
René van Bevern, Till Fluschnik, George B. Mertzios +3
This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feed…
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…
h-Index Manipulation by Undoing Merges
René van Bevern, Christian Komusiewicz, Hendrik Molter +3
The h-index is an important bibliographic measure used to assess the performance of researchers. Dutiful researchers merge different versions of their articles in their Google Scho…
A fixed-parameter algorithm for a routing open shop problem: unit processing times, few machines and locations
René van Bevern, Artem V. Pyatkin
The open shop problem is to find a minimum makespan schedule to process each job on each machine for time such that, at any time, each machine processes at mos…
Exploiting Hidden Structure in Selecting Dimensions that Distinguish Vectors
Vincent Froese, René van Bevern, Rolf Niedermeier +1
The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main resul…
Parameterizing edge modification problems above lower bounds
René van Bevern, Vincent Froese, Christian Komusiewicz
We study the parameterized complexity of a variant of the -free Editing problem: Given a graph and a natural number , is it possible to modify at most edges in so…
The role of twins in computing planar supports of hypergraphs
René van Bevern, Iyad A. Kanj, Christian Komusiewicz +2
A support or realization of a hypergraph is a graph on the same vertex as such that for each hyperedge of it holds that its vertices induce a connected subgraph of…
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
René van Bevern, Rolf Niedermeier, Ondřej Suchý
We study the problem of non-preemptively scheduling jobs, each job with a release time , a deadline , and a processing time , on parallel identical machi…
Well-Formed Separator Sequences, with an Application to Hypergraph Drawing
René van Bevern, Iyad Kanj, Christian Komusiewicz +2
Given a hypergraph , the Planar Support problem asks whether there is a planar graph on the same vertex set as such that each hyperedge induces a connected subgraph of $…