Log-space Constructible Universal Traversal Sequences for Cycles of Length O(n403)

摘要

The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even N C 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.