Distributed graph problems through an automata-theoretic lens

Yi-Jun Chang, Jan Studený, Jukka Suomela

The locality of a graph problem is the smallest distance $T$ such that each node can choose its own part of the solution based on its radius-$T$ neighborhood. In many settings, a g…