Sandpile prediction on a tree in near linear time
Akshay Ramachandran, Aaron Schild · 2017
In the sandpile model, we are given an undirected graph G and an initial list of chip counts on each vertex of G and we may fire degree(v) chips from any vertex v to its neighbors. Doing chip moves either results in a unique terminal configuration or recurs forever. On many families of graphs - including trees - the problem of computing the final configuration is P-complete [13] and simulation can take as long as Θ(n3) time. We give a O(n log5 n) time algorithm for trees that computes the terminal configuration or shows that chip firing will not terminate.