18 citations · 23 across the 12 of their papers we have counts for
15 papers
How to Resolve Envy by Adding Goods
Matthias Bentert, Robert Bredereck, Eva Deltl +2
We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be r…
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…
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…
Using a geometric lens to find k disjoint shortest paths
Matthias Bentert, André Nichterlein, Malte Renken +1
Given an undirected -vertex graph and pairs of terminal vertices , the -Disjoint Shortest Paths (-DSP)-problem asks whether there are …