2 citations · 4 across the 5 of their papers we have counts for
5 papers
Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
Matthias Bentert, Klaus Heeger, Tomohiro Koana
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal i…
Threshold Testing and Semi-Online Prophet Inequalities
Martin Hoefer, Kevin Schewior
We study threshold testing, an elementary probing model with the goal to choose a large value out of i.i.d. random variables. An algorithm can test each variable once for…
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
Matthias Bentert, Niclas Boehmer, Klaus Heeger +1
We study stable matching problems where agents have multilayer preferences: There are layers each consisting of one preference relation for each agent. Recently, Chen et al.…
Who won? Winner Determination and Robustness in Liquid Democracy
Matthias Bentert, Niclas Boehmer, Maciej Rymar +1
Liquid democracy is a decision-making paradigm in which each agent can either vote directly for some alternative or (transitively) delegate its vote to another agent. To mitigate t…
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
Matthias Bentert, Klaus Heeger, Dušan Knop
In the presented paper we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph , two v…