Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n{sup}4.03)

摘要

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