18 citations · 23 across the 12 of their papers we have counts for
11 papers · 1 filter
The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
Matthias Bentert, Leon Kellerhals, Rolf Niedermeier
We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where…
Fair Short Paths in Vertex-Colored Graphs
Matthias Bentert, Leon Kellerhals, Rolf Niedermeier
The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally v…
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…
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…
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…
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…
Parameterized Aspects of Triangle Enumeration
Matthias Bentert, Till Fluschnik, André Nichterlein +1
The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertic…