3 citations · 4 across the 8 of their papers we have counts for
5 papers · 1 filter
Faster Approximate Fixed Points of -Contractions
Andrei Feodorov, Sebastian Haslebacher
We present a new algorithm for finding an -approximate fixed point of an -contracting function . Our algorithm is based on the qu…
A Levelset Algorithm for 3D-Tarski
Sebastian Haslebacher, Jonas Lill
We present a simple new algorithm for finding a Tarski fixed point of a monotone function . Our algorithm runs in time and makes $O(\log^…
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…
ARRIVAL: Recursive Framework & -Contraction
Sebastian Haslebacher
ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, accordi…
A Subexponential Algorithm for ARRIVAL
Bernd Gärtner, Sebastian Haslebacher, Hung P. Hoang
The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in $NP \cap…