Polynomial Bound for a Chip Firing Game on Graphs

DOI10.1137/0401039zbMath0652.68089OpenAlexW2026915189MaRDI QIDQ3798269

Gábor Tardos

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401039

zbMATH Keywords

polynomial timechip firing game on graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models ⋮ No polynomial bound for the period of the parallel chip firing game on graphs ⋮ Riemann-Roch and Abel-Jacobi theory on a finite graph ⋮ Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three ⋮ On the sandpile group of regular trees ⋮ Abelian sandpile model and Biggs-Merino polynomial for directed graphs ⋮ Universality of the chip-firing game ⋮ On approximating the rank of graph divisors ⋮ Abelian networks. II: Halting on all inputs ⋮ Compatible recurrent identities of the sandpile group and maximal stable configurations ⋮ No Polynomial Bound for the Chip Firing Game on Directed Graphs ⋮ Parallel chip firing games on graphs ⋮ Chip-firing games on directed graphs ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ On the complexity of sandpile critical avalanches ⋮ The Complexity of Three-Dimensional Critical Avalanches ⋮ A constant bound for the periods of parallel chip-firing games with many chips ⋮ Unnamed Item ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ CoEulerian graphs ⋮ The chip firing game on \(n\)-cycles ⋮ On the Complexity of Sandpile Prediction Problems ⋮ Properties of chip-firing games on complete graphs ⋮ Abelian Logic Gates ⋮ Gonality Sequences of Graphs ⋮ Random Walks, Electric Networks and The Transience Class problem of Sandpiles ⋮ Source reversal and chip firing on graphs ⋮ An exact bound on the number of chips of parallel chip-firing games that stabilize ⋮ The chip-firing game ⋮ Chip-firing games on graphs

This page was built for publication: Polynomial Bound for a Chip Firing Game on Graphs