Lower bounds on the length of universal traversal sequences
From MaRDI portal
Publication:1201151
DOI10.1016/0022-0000(92)90046-LzbMath0754.68061MaRDI QIDQ1201151
Allan Borodin, Walter L. Ruzzo, Martin Tompa
Publication date: 17 January 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, On the mean and variance of cover times for random walks on graphs, The electrical resistance of a graph captures its commute and cover times
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
