Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques (Q1117703): Difference between revisions

Explicit construction of universal traversal sequences of polynomial length for regular graphs is an open problem which was solved only for cycles. \textit{A. Bar-Noy}, \textit{A. Borodin}, \textit{M. Karchmer}, \textit{N. Liníal} and \textit{M. Werman} [SIAM J. Comput. 18, No.2, 268-277 (1989)] found universal sequences of length \(n^{\theta (n^ 2)}\) for cliques. The result is improved in this paper; the authors give a method to construct shorter universal traversal sequences for this class of regular graphs. These sequences have length \(n^{O(\log n)}\) and can be constructed uniformly in \(\log^ 2 n\) space.