Springe direkt zu Inhalt

Banafshe Sadeghi:

An Introduction to and Experimental Examination of The Arrival Game

Kurzbeschreibung

The Arrival game is a zero-player game on switch graphs. Switch graphs are graphs in which the vertices have at most two outgoing edges to their successors and the successors are switched successively when traversed. In the case of Arrival a switch graph is given, an origin and a destination in that graph and the problem Arrival is to decide whether a run through the switch graph starting at the origin will at some point arrive at the destination.

Arrival’s complexity is of interest because Arrival has been proven to lie in the intersection of UP and co-UP but there has yet not been found a polynomial-time algorithm to solve it.

We present previous research on Arrival’s complexity as well as introduce an experimental examination of the solutions of Arrival for small switch graphs. The following work is to be seen as an introduction to Arrival. The experimental part shall give a hint on the runtime of YES-instances of Arrival.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
10.11.2020