Algorithmic aspects of the reachability of conflicting chip firing game

Abstract

Chip-firing game is a cellular automaton model on finite directed graphs often used to describe the phenomenon of self-organized criticality. Here we investigate a variation of the chip-firing game on a directed acyclic graph G??=??(V, E). Starting from a given chip configuration, we can fire a vertex v by sending one chip along one of its outgoing edges to the corresponding neighbors if v has at least one chip. We study the reachability of this system by considering the order structure of its configuration space. Then we propose an efficient algorithm to determine this reachability. ?? 2010 Springer-Verlag Berlin Heidelberg.