A cellular automaton that solves distributed spanning tree problem

This work introduces the distributed spanning tree problem in the domain of cellular automata. We present a cellular automaton that computes a spanning tree of a given (grid) graph. The time required for this computation is O(nlogn), where n is the number of nodes of the graph.