Chip-firing games on directed graphs

DOI10.1023/A:1022467132614zbMath0805.90142OpenAlexW105010561MaRDI QIDQ685991

Publication date: 31 January 1995

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1022467132614

zbMATH Keywords

reachability Laplace operator Petri net chip-firing game probabilistic abacus reandom walk vector addition system

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Games involving graphs (91A43) Directed graphs (digraphs), tournaments (05C20)

Related Items

Chip-firing game and a partial Tutte polynomial for Eulerian digraphs ⋮ Dynamic graph models and their properties ⋮ Reachability is decidable in the numbers game ⋮ Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ Multi-Eulerian tours of directed graphs ⋮ Sandpile models and lattices: a comprehensive survey ⋮ The sandpile group of a thick cycle graph ⋮ Riemann-Roch and Abel-Jacobi theory on a finite graph ⋮ Abelian networks IV. Dynamics of nonhalting networks ⋮ Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three ⋮ On the sandpile group of regular trees ⋮ Strong convergence and the polygon property of 1-player games ⋮ A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case ⋮ Abelian sandpile model and Biggs-Merino polynomial for directed graphs ⋮ Chip firing and the Tutte polynomial ⋮ Universality of the chip-firing game ⋮ A study of Euler resource networks ⋮ Chip-firing based methods in the Riemann-Roch theory of directed graphs ⋮ On approximating the rank of graph divisors ⋮ Algorithmic aspects of rotor-routing and the notion of linear equivalence ⋮ Classes of lattices induced by chip firing (and sandpile) dynamics. ⋮ Unnamed Item ⋮ Geometric and spectral analysis on weighted digraphs ⋮ Abelian networks. II: Halting on all inputs ⋮ Chip-Firing Games and Critical Groups ⋮ Compatible recurrent identities of the sandpile group and maximal stable configurations ⋮ Control of limit states in absorbing resource networks ⋮ Experimental research on the welfare in a closed production network ⋮ Chip firing on Dynkin diagrams and McKay quivers ⋮ ULD-Lattices and Δ-Bonds ⋮ Spanning trees and recurrent configurations of a graph ⋮ Strict partitions and discrete dynamical systems ⋮ Height probabilities in the Abelian sandpile model on the generalized finite Bethe lattice ⋮ Markov chain methods for analyzing urban networks ⋮ Strong emergence of wave patterns on Kadanoff sandpiles ⋮ The sandpile group of a family of nearly complete graphs ⋮ Random walks and flights over connected graphs and complex networks ⋮ CoEulerian graphs ⋮ Resource allocation among attractor vertices in asymmetric regular resource networks ⋮ Resource network with limited capacity of attractor vertices ⋮ A maximizing characteristic for critical configurations of chip-firing games on digraphs ⋮ On the Complexity of Sandpile Prediction Problems ⋮ Properties of chip-firing games on complete graphs ⋮ Root system chip-firing. I: Interval-firing ⋮ Rotor-routing reachability is easy, chip-firing reachability is hard ⋮ Chip-firing and the critical group of a graph ⋮ Source reversal and chip firing on graphs ⋮ Unnamed Item ⋮ A survey on the stability of (extended) linear Sand Pile model ⋮ Chip-Firing, Antimatroids, and Polyhedra ⋮ Growth of replacements ⋮ The chip-firing game ⋮ On the complexity of the chip-firing reachability problem ⋮ Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs

Cites Work