Polynomial Bound for a Chip Firing Game on Graphs

DOI10.1137/0401039MaRDI QIDQ3798269zbMATH OpenOpenAlexFDO

Authors 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

chip firing game on graphspolynomial time

Mathematics Subject Classification ID

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

Recommendations

• No Polynomial Bound for the Chip Firing Game on Directed Graphs
• Algorithmic aspects of a chip-firing game
• No polynomial bound for the period of the parallel chip firing game on graphs
• A constant bound for the periods of parallel chip-firing games with many chips
• Chip-firing games on graphs

Cited in

(35)

• Parallel chip firing games on graphs
• No polynomial bound for the period of the parallel chip firing game on graphs
• Universality of the chip-firing game
• Source reversal and chip firing on graphs
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• The chip firing game on \(n\)-cycles
• A chip-firing game and Dirichlet eigenvalues
• An exact bound on the number of chips of parallel chip-firing games that stabilize
• Compatible recurrent identities of the sandpile group and maximal stable configurations
• On graph parameters guaranteeing fast sandpile diffusion
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• The chip-firing game
• CoEulerian graphs
• On the complexity of sandpile prediction problems
• No Polynomial Bound for the Chip Firing Game on Directed Graphs
• scientific article; zbMATH DE number 32904 (Why is no real title available?)
• scientific article; zbMATH DE number 1741027 (Why is no real title available?)
• Some halting problems for abelian sandpiles are undecidable in dimension three
• The length distribution for burn-off chip-firing games on complete graphs
• Chip-Firing Games on Mutating Graphs
• The complexity of three-dimensional critical avalanches
• Gonality sequences of graphs
• Toppling numbers of complete and random graphs
• Abelian logic gates
• On the complexity of sandpile critical avalanches
• Random walks, electric networks and the transience class problem of sandpiles
• Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models
• Recognizing hyperelliptic graphs in polynomial time
• On approximating the rank of graph divisors
• Chip-firing games on directed graphs
• A constant bound for the periods of parallel chip-firing games with many chips
• Properties of chip-firing games on complete graphs
• Chip-firing games on graphs
• On the sandpile group of regular trees
• Abelian networks. II: Halting on all inputs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798269)