7 papers
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
Matthias Bentert, Robert Bredereck, Péter Györgyi +2
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing…
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Matthias Bentert, Tomohiro Koana, Rolf Niedermeier
Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. Whi…
Parameterized Complexity of Min-Power Asymmetric Connectivity
Matthias Bentert, Roman Haag, Christian Hofer +2
We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-w…
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Anne-Sophie Himmel, Matthias Bentert, André Nichterlein +1
Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed ve…
Listing All Maximal -Plexes in Temporal Graphs
Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter +3
Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (…
Parameterized Complexity of Diameter
Matthias Bentert, André Nichterlein
Diameter -- the task of computing the length of a longest shortest path -- is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no $O(n^{1.99})…