Log-space constructible universal traversal sequences for cycles of length O(n^4.03).

DOI10.1016/S0304-3975(02)00436-XMaRDI QIDQ1401264zbMATH OpenFDO

Authors Michal Koucký

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(02)00436-X

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1796948
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• Universal traversal sequences for paths and cycles
• Lower bounds on universal traversal sequences based on chains of length five

Cites work

• Bounds on Universal Sequences
• scientific article; zbMATH DE number 1256637 (Why is no real title available?)
• scientific article; zbMATH DE number 1796968 (Why is no real title available?)
• Pseudorandom generators for space-bounded computation
• Universal traversal sequences for expander graphs
• Universal traversal sequences for paths and cycles
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques

Cited in

(8)

• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Length lower bounds for reflecting sequences and universal traversal sequences
• Graph exploration by a finite automaton
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• Universal Traversal Sequences
• scientific article; zbMATH DE number 1796948 (Why is no real title available?)
• Memory Efficient Anonymous Graph Exploration
• Impact of memory size on graph exploration capability

This page was built for publication: Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401264)