✦ LIBER ✦
Log-space constructible universal traversal sequences for cycles of length O(n4.03)
✍ Scribed by Michal Koucký
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 268 KB
- Volume
- 296
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
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.