Artículo Original
Publicado 2006-10-24
Palabras clave
- pilas de arena,
- laplacianos de grafos,
- autómatas celulares,
- complejidad
Cómo citar
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. Recuperado a partir de https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/258
Resumen
En este artículo estudiamos el Modelo de Pilas de Arena sobre grafos dirigidos. El comportamiento del modelo sobre grafos dirigidos es más complejo (en término estrictos) que sobre grafos no dirigidos; es por ello que, para muchas de las preguntas centrales de la teoría, no se conoce la respuesta en el caso dirigido. En este artículo se ha sintetizado la teoría para digrafos, se han simplificado algunas pruebas y se concretan algunos resultados relacionados con la complejidad de predicción del autómata.
Descargas
Los datos de descargas todavía no están disponibles.
Referencias
[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.