66 citations · 457 across the 33 of their papers we have counts for
13 papers · 1 filter
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…
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…
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 $…
Network-Based Vertex Dissolution
René van Bevern, Robert Bredereck, Jiehua Chen +3
We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an…
Partitioning Perfect Graphs into Stars
René van Bevern, Robert Bredereck, Laurent Bulteau +4
The partition of graphs into "nice" subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size st…
Interval scheduling and colorful independent sets
René van Bevern, Matthias Mnich, Rolf Niedermeier +1
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an…
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
René van Bevern, Andreas Emil Feldmann, Manuel Sorge +1
A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition t…
Myhill-Nerode methods for hypergraphs
René van Bevern, Rodney G. Downey, Michael R. Fellows +2
We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We prov…
Towards Optimal and Expressive Kernelization for d-Hitting Set
René van Bevern
d-Hitting Set is the NP-hard problem of selecting at most k vertices of a hypergraph so that each hyperedge, all of which have cardinality at most d, contains at least one selected…
Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion
René van Bevern
We introduce the s-Plex Cluster Vertex Deletion problem. Like the Cluster Vertex Deletion problem, it is NP-hard and motivated by graph-based data clustering. While the task in Clu…