ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > BINARY SEQUENCES:
Reports tagged with binary sequences:
TR01-013 | 2nd February 2001
Michal Koucký

Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{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^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. more >>>



ISSN 1433-8092 | Imprint