Search Marches de... as keywords on MyScienceWork's publications...

In this thesis we focus on the algorithmic properties of a cellular automaton known as rotor walks This model has been introduced in two distinct ways Firstly as a fundamental operation within another cellular automaton known as Sandpiles which models the collapse of a sand pile when it becomes too high Secondly due to its resemblance to well-studied stochastic models such as random walks Indeed numerous structural properties of random walks hitting times cover times etc are analogous to those of this completely deterministic automaton called the rotor walk The main motivation for this thesis stems from this derandomization of a random process More precisely a rotor walk corresponds to the movement of a particle on a directed graph following the following rule initially an order a numbering is fixed on the outgoing arcs of each vertex of the graph Once the starting position of the particle is defined each time it is on a vertex it leaves through the arc with the lowest value that it has not already used Of course if all arcs have been used the process restarts with the lowest value arc There is a multitude of accessibility problems on rotors and we aim to compile a list of them in this thesis We also provide complexity results for some of these problems Subsequently we turn our attention to a specific accessibility problem ARRIVAL Considering a graph with sinks such that there is a directed path between each vertex of the graph and at least one of these sinks a rotor walk inevitably terminates Unfortunately the number of steps before this process concludes can be exponential In 2017 Dorhau et al introduced a problem called ARRIVAL which seeks to determine if the particle successfully reaches a given sink They demonstrated that it belongs to the complexity classes NP and co-NP Being a strong candidate for polynomial algorithm resolution we investigate this problem on a subclass of graphs where the step count of the process can be exponential Tree-like multigraphs These are multigraphs whose underlying undirected graph is a tree In this context we show that this problem can be solved in linear time extending these results to decision versions of the ARRIVAL problem known to be respectively NP-complete and PSPACE-complete

Publication search with Marches de rotors as keyword

Reachability problems for general rotor walks in graphs

Publication search
with Marches de rotors as keyword