Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques

DOI10.1016/0020-0190(88)90197-4zbMath0667.68078OpenAlexW2070042895MaRDI QIDQ1117703

Howard J. Karloff, Janos Simon, Ramamohan Paturi

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90197-4

zbMATH Keywords

regular graphscliquesexplicit constructionspace-bounded computationuniversal sequencesuniversal traversal sequences

Mathematics Subject Classification ID

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

Related Items (10)

Universal traversal sequences with backtracking. ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). ⋮ Impact of memory size on graph exploration capability ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Lower bounds on the length of universal traversal sequences ⋮ Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs ⋮ Pseudorandom generators for space-bounded computation ⋮ Universal traversal sequences for expander graphs ⋮ Graph exploration by a finite automaton

Cites Work

• Unnamed Item
• Bounds on Universal Sequences
• Universal traversal sequences for paths and cycles

This page was built for publication: Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques