3 papers
cs.DS2018
Optimal strategies for patrolling fences
Bernhard Haeupler, Fabian Kuhn, Anders Martinsson +2
A classical multi-agent fence patrolling problem asks: What is the maximum length of a line that agents with maximum speeds can patrol if each point on the…
cs.DM2016
Unique reconstruction threshold for random jigsaw puzzles
Rajko Nenadov, Pascal Pfister, Angelika Steger
A random jigsaw puzzle is constructed by arranging square pieces into an grid and assigning to each edge of a piece one of available colours uniformly at ran…
cs.DM2015
Strong games played on random graphs
Asaf Ferber, Pascal Pfister
In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). Th…