5 papers
On the Multi-Robber Damage Number
MiloÅ¡ StojakoviÄ, Lasse Wulf
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with on…
The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
Marc Goerigk, Dorothee Henke, Lasse Wulf
A standard type of uncertainty set in robust optimization is budgeted uncertainty, where an interval of possible values for each parameter is given and the total deviation from the…
Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
Lasse Wulf
The diameter of a polytope is a fundamental geometric parameter that plays a crucial role in understanding the efficiency of the simplex method. Despite its central nature, the com…
Fréchet Distance in Unweighted Planar Graphs
Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg +1
The Fréchet distance is a distance measure between trajectories in or walks in a graph . Given constant-time shortest path queries, the Discrete Fréchet distance $…
On Finding -th Smallest Perfect Matchings
Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1
Given an undirected weighted graph and an integer , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly in . In this p…