Lower bounds on the length of universal traversal sequences
From MaRDI portal
Publication:1201151
DOI10.1016/0022-0000(92)90046-LzbMATH Open0754.68061OpenAlexW2949147209MaRDI QIDQ1201151FDOQ1201151
Authors: 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)
Full work available at URL: https://doi.org/10.1016/0022-0000(92)90046-l
Recommendations
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- scientific article; zbMATH DE number 15261
- Lower bounds on universal traversal sequences based on chains of length five
- Universal traversal sequences for paths and cycles
- Length lower bounds for reflecting sequences and universal traversal sequences
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Computational Complexity of Probabilistic Turing Machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the cover time of random walks on graphs
- Space Lower Bounds for Maze Threadability on Restricted Machines
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- Two Applications of Inductive Counting for Complementation Problems
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- Universal sequences for complete graphs
- Lower bounds on probabilistic linear decision trees
- Title not available (Why is that?)
Cited In (17)
- Universal sequences for complete graphs
- Edge exploration of anonymous graph by mobile agent with external help
- Title not available (Why is that?)
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- The electrical resistance of a graph captures its commute and cover times
- Lower bounds on universal traversal sequences based on chains of length five
- Universal traversal sequences for expander graphs
- Title not available (Why is that?)
- Bounds on Universal Sequences
- Universal traversal sequences with backtracking.
- Universal traversal sequences for paths and cycles
- Lower bounds on lengths of checking sequences
- Lower bounds for the length of test sequences using UIOs
- Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
- On the mean and variance of cover times for random walks on graphs
- Length lower bounds for reflecting sequences and universal traversal sequences
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
This page was built for publication: Lower bounds on the length of universal traversal sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201151)
