Bounds on Universal Sequences
From MaRDI portal
Publication:3472132
DOI10.1137/0218018zbMath0696.05035OpenAlexW2065686270MaRDI QIDQ3472132
Allan Borodin, Amotz Bar-Noy, Nathan Linial, Michael Werman, Mauricio Karchmer
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218018
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items
Universal traversal sequences with backtracking., Memory Efficient Anonymous Graph Exploration, Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques, Length lower bounds for reflecting sequences and universal traversal sequences, Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\))., Improved length lower bounds for reflecting sequences, Universal sequences for complete graphs, 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, Graph exploration by a finite automaton
