Algorithmic aspects of a chip-firing game
A variant of the chip-firing game (see \textit{A. Björner} et al. [Eur. J. Comb. 12, No. 4, 283-291 (1991; Zbl 0729.05048)]), namely a slight generalization of the dollar game introduced by \textit{N. L. Biggs} [J. Algebr. Comb. 9, No. 1, 25-45 (1999; Zbl 0919.05027)] is studied. The game is played on a graph with a (possibly negative) number of chips on each vertex. A vertex can fire, i.e. give one chip to each of its neighbors, if it has at least as many chips as incident edges. There is one special vertex, called the government, which can be fired independently of the number of chips there. If only the government can fire, the configuration is called stable. A configuration is critical, if it is both stable and recurrent. In the paper under review it is proved that the number of steps needed to reach a critical configuration is polynomial in the number of edges of the graph and the number of chips in the starting configuration. The main tool used in analysing the discrete dollar game is its continuous version called the oil game, whose statics as well as dynamics are developed.
- Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
- Chip-firing and the critical group of a graph
- Chip-firing games, potential theory on graphs, and spanning trees
- A maximizing characteristic for critical configurations of chip-firing games on digraphs
- The Tutte polynomial as a growth function
- Lattices generated by chip firing game models: criteria and recognition algorithms
- Growth of replacements
- Compatible recurrent identities of the sandpile group and maximal stable configurations
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Polynomial Bound for a Chip Firing Game on Graphs
- No Polynomial Bound for the Chip Firing Game on Directed Graphs
- Biggs's game
- On lengths of burn-off chip-firing games
- Experimental research on the welfare in a closed production network
- Toppling numbers of complete and random graphs
- The lattice structure of chip firing games and related models
- A greedy chip‐firing game
- Order structure and energy of conflicting chip firing game
- Properties of chip-firing games on complete graphs
- Chip-firing games on graphs
- On the sandpile group of regular trees
- Meteor process on \({\mathbb Z}^d\)
This page was built for publication: Algorithmic aspects of a chip-firing game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2777901)
