Original article
Published 2006-10-24
Keywords
- pilas de arena,
- laplacianos de grafos,
- autómatas celulares,
- complejidad
How to Cite
Mejía Moreno, C. (2006). Pilas de arena sobre grafos dirigidos y algo de complejidad. Revista Integración, Temas De matemáticas, 24(2), 101–116. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/258
Abstract
In this work we study the Abelian Sandpile Model on directed graphs. The model is more complex on directed graphs than on undirected graphs, because of which there are many questions that remain without an answer. We survey the basic theory of the model on directed graphs and present some new results.
Downloads
Download data is not yet available.
References
[1] L. Babai. The Abelian Sandpile Model. Manuscrito, disponible en http://people.cs.uchicago.edu/~laci/REU05/.
[2] N. Biggs. “Chip-firing and the critical group of a graph”. J. Algebraic Combinatory. 9(1):25-45, 1999.
[3] A. Bjorner & L. Lovasz. “Chip firing games on directed graphs”. European J. Combinatorics. 12(4):305-328, 1992.
[4] F. Chung & R. Ellis. “A chip-firing game and Dirichlet eigenvalues”. Discrete Mathematics, 257:341-355, 2002.
[5] D. Dhar. “Self Organized Critical State of the Sandpile Automaton Model”. Physical Review Letters, 64(14): 1613-1616, 1990.
[6] K. Eriksson. “No polynomial bound for the Chip firing game on directed graphs”. Proceedings American Mathematical Society, 112:1203-1205, 1991.
[7] N. Jacobson. Basic Algebra. W.H. Freeman, San Francisco, 1971.
[8] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[9] G. Tardos. “Polynomial bound for a chip firing game on graphs”. SIAM J. Discrete Mathematics, 1:397-398, 1988.
[10] E. Toumpakari. On the abelian sandpile model. Ph.D. thesis, Universidad de Chicago, 2005.
[11] L.G. Valiant & V. Vazirani. “NP is as easy as detecting unique solutions”. Theoretical computer Science, 47:85-93, 1986.
[2] N. Biggs. “Chip-firing and the critical group of a graph”. J. Algebraic Combinatory. 9(1):25-45, 1999.
[3] A. Bjorner & L. Lovasz. “Chip firing games on directed graphs”. European J. Combinatorics. 12(4):305-328, 1992.
[4] F. Chung & R. Ellis. “A chip-firing game and Dirichlet eigenvalues”. Discrete Mathematics, 257:341-355, 2002.
[5] D. Dhar. “Self Organized Critical State of the Sandpile Automaton Model”. Physical Review Letters, 64(14): 1613-1616, 1990.
[6] K. Eriksson. “No polynomial bound for the Chip firing game on directed graphs”. Proceedings American Mathematical Society, 112:1203-1205, 1991.
[7] N. Jacobson. Basic Algebra. W.H. Freeman, San Francisco, 1971.
[8] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[9] G. Tardos. “Polynomial bound for a chip firing game on graphs”. SIAM J. Discrete Mathematics, 1:397-398, 1988.
[10] E. Toumpakari. On the abelian sandpile model. Ph.D. thesis, Universidad de Chicago, 2005.
[11] L.G. Valiant & V. Vazirani. “NP is as easy as detecting unique solutions”. Theoretical computer Science, 47:85-93, 1986.