Complexity of Deciding Sense of Direction
Paolo Boldi, Sebastiano Vigna · SIAM Journal on Computing · 2000
In this paper we prove that deciding whether a distributed system (represented as a colored digraph with n nodes) has weak sense of direction is in AC 1 (using n 6 processors). Moreover, we show that deciding sense of direction is in P. Our algorithms can also be used to decide in AC 1 whether a colored graph is a Cayley color graph.