Lower bounds on the length of universal traversal sequences

DOI10.1016/0022-0000(92)90046-LMaRDI QIDQ1201151zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity of graph traversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Bounds on Universal Sequences
• Computational Complexity of Probabilistic Turing Machines
• scientific article; zbMATH DE number 5995471 (Why is no real title available?)
• scientific article; zbMATH DE number 4062584 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• Lower bounds on probabilistic linear decision trees
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• On the cover time of random walks on graphs
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Two Applications of Inductive Counting for Complementation Problems
• Universal sequences for complete graphs
• Universal traversal sequences for paths and cycles
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques

Cited in

(18)

• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• 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
• Universal traversal sequences for expander graphs
• Universal traversal sequences with backtracking.
• Lower bounds on universal traversal sequences based on chains of length five
• Length lower bounds for reflecting sequences and universal traversal sequences
• Bounds on Universal Sequences
• Universal traversal sequences for paths and cycles
• scientific article; zbMATH DE number 15261 (Why is no real title available?)
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• scientific article; zbMATH DE number 1796968 (Why is no real title available?)
• Lower bounds for the length of test sequences using UIOs
• Lower bounds on lengths of checking sequences
• Improved length lower bounds for reflecting sequences
• Edge exploration of anonymous graph by mobile agent with external help
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• Universal sequences for complete graphs

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)