Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-013 | 2nd February 2001 00:00

Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{4.03})$

RSS-Feed




TR01-013
Authors: Michal Koucky
Publication: 12th February 2001 14:59
Downloads: 4101
Keywords: 


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.



ISSN 1433-8092 | Imprint