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

• 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?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Bounds on Universal Sequences
• Computational Complexity of Probabilistic Turing Machines
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• Lower bounds on probabilistic linear decision trees
• 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 sequences for complete graphs
• Lower bounds for the length of test sequences using UIOs
• Length lower bounds for reflecting sequences and universal traversal sequences
• The electrical resistance of a graph captures its commute and cover times
• Improved length lower bounds for reflecting sequences
• Lower bounds on universal traversal sequences based on chains of length five
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• scientific article; zbMATH DE number 1796968 (Why is no real title available?)
• Edge exploration of anonymous graph by mobile agent with external help
• scientific article; zbMATH DE number 15261 (Why is no real title available?)
• Universal traversal sequences for paths and cycles
• Universal traversal sequences with backtracking.
• On the mean and variance of cover times for random walks on graphs
• Universal traversal sequences for expander graphs
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
• Lower bounds on lengths of checking sequences
• Bounds on Universal Sequences

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)