Abstract:
The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even $NC^1$) constructible and are of length $O(n^{4.03})$. Our result improves the previously known upper-bound $O(n^{4.76})$ for log-space constructible universal traversal sequences for cycles.