Constructing Generalized Universal Traversing Sequences (Extended Abstract)
Sorin Istrail · 1990
The paper constructs a gen- eralized version of universal traversing sequences. The generalization preserves the features of the universal travers- ing sequences that make them attractive for applications to derandomizations and space-bounded computation. For every n, a sequence is constructed that is used by a finite-automaton with 0(1) states in order to traverse all the n-vertex la- beled undirected graphs. The automa- ton walks on the graph; when it is at a certain vertex, it uses the edge labels and the sequence in order to decide which edge to follow. When walking on an edge, the automaton can see the edge la- beling. The generalized sequences have size 2°(8()) and traverse all the n-vertex undirected graphs G satisfying