Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
From MaRDI portal
Publication:1117703
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
regular graphscliquesexplicit constructionspace-bounded computationuniversal sequencesuniversal traversal sequences
Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)
Related Items
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
