Pilas de arena sobre grafos dirigidos y algo de complejidad
No Thumbnail Available
Date
Authors
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
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.
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.
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.
Keywords
pilas de arena, laplacianos de grafos, autómatas celulares, complejidad