Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC LOG-SPACE:
Reports tagged with symmetric log-space:
TR01-013 | 2nd February 2001
Michal Koucky

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