We discuss a very close relation between minimal recurrent configurations of Chip Firing Games and Directed Acyclic Graphs and demonstrate the usefulness of this relation by giving a lower bound for the number of minimal recurrent configurations of the Abelian Sandpile Model as well as a lower bound for the number of firings which are caused by the addition of two recurrent configurations on particular graphs.
Volume: DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Chip Firing Games,Sandpile Model,Minimal Recurrent Configurations,DAGs,Addition of Recurrent Configurations,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
1 Document citing this article
Source : OpenCitations
Perrot, KĂŠvin; Van Pham, Trung, 2015, Feedback Arc Set Problem And NP-Hardness Of Minimum Recurrent Configuration Problem Of Chip-Firing Game On Directed Graphs, Annals Of Combinatorics, 19, 2, pp. 373-396, 10.1007/s00026-015-0266-9.