6 papers · 1 filter
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})…
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Matthias Bentert, Alexander Dittmann, Leon Kellerhals +2
Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a…