2 citations · 4 across the 7 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024★ 2 cited
On the Complexity of the Bilevel Shortest Path Problem
Dorothee Henke, Lasse Wulf
We introduce a new bilevel version of the classic shortest path problem and completely characterize its computational complexity with respect to several problem variants. In our pr…
cs.CC2024
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Christoph Grüne, Lasse Wulf
Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consid…
cs.CG2024★ 2 cited
Recognition of Unit Segment and Polyline Graphs is -Complete
Michael Hoffmann, Tillmann Miltzow, Simon Weber +1
Given a set of objects in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corres…