Geodesic
Chip-firing games on directed graphs
Journal of Algebraic Combinatorics, Tome 1 (1992) no. 4, pp. 305-328.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects. Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable.
Keywords: chip-firing game, vector addition system, reachability, random walk, probabilistic abacus, Laplace operator, Petri net 
@article{JAC_1992__1_4_a4,
     author = {Bj\"orner, Anders and Lov\'asz, L\'aszl\'o},
     title = {Chip-firing games on directed graphs},
     journal = {Journal of Algebraic Combinatorics},
     pages = {305--328},
     publisher = {mathdoc},
     volume = {1},
     number = {4},
     year = {1992},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_1992__1_4_a4/}
}
TY  - JOUR
AU  - Björner, Anders
AU  - Lovász, László
TI  - Chip-firing games on directed graphs
JO  - Journal of Algebraic Combinatorics
PY  - 1992
SP  - 305
EP  - 328
VL  - 1
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_1992__1_4_a4/
LA  - en
ID  - JAC_1992__1_4_a4
ER  - 
%0 Journal Article
%A Björner, Anders
%A Lovász, László
%T Chip-firing games on directed graphs
%J Journal of Algebraic Combinatorics
%D 1992
%P 305-328
%V 1
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_1992__1_4_a4/
%G en
%F JAC_1992__1_4_a4
Björner, Anders; Lovász, László. Chip-firing games on directed graphs. Journal of Algebraic Combinatorics, Tome 1 (1992) no. 4, pp. 305-328. http://geodesic.mathdoc.fr/item/JAC_1992__1_4_a4/