Lower bounds on the length of universal traversal sequences
From MaRDI portal
Publication:1201151
DOI10.1016/0022-0000(92)90046-LzbMath0754.68061OpenAlexW2949147209MaRDI QIDQ1201151
Martin Tompa, Walter L. Ruzzo, Allan Borodin
Publication date: 17 January 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(92)90046-l
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (5)
Universal traversal sequences with backtracking. ⋮ On the mean and variance of cover times for random walks on graphs ⋮ Length lower bounds for reflecting sequences and universal traversal sequences ⋮ The electrical resistance of a graph captures its commute and cover times ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Universal sequences for complete graphs
- Lower bounds on probabilistic linear decision trees
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- On the cover time of random walks on graphs
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- Two Applications of Inductive Counting for Complementation Problems
- Space Lower Bounds for Maze Threadability on Restricted Machines
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- Computational Complexity of Probabilistic Turing Machines
This page was built for publication: Lower bounds on the length of universal traversal sequences
