3 papers
cs.DS2023
Delaying Decisions and Reservation Costs
Elisabet Burjons, Fabian Frei, Matthias Gehnen +3
We study the Feedback Vertex Set and the Vertex Cover problem in a natural variant of the classical online model that allows for delayed decisions and reservations. Both problems c…
cs.DS2023
Zero-Memory Graph Exploration with Unknown Inports
Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger +1
We study a very restrictive graph exploration problem. In our model, an agent without persistent memory is placed on a vertex of a graph and only sees the adjacent vertices. The go…
cs.DS2023
Bounds for c-Ideal Hashing
Fabian Frei, David Wehner
In this paper, we analyze hashing from a worst-case perspective. To this end, we study a new property of hash families that is strongly related to d-perfect hashing, namely c-ideal…