Universal traversal sequences with backtracking.

DOI10.1016/S0022-0000(02)00023-5zbMath1059.68080MaRDI QIDQ1872734

Michal Koucký

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

exploration sequences

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

Memory Efficient Anonymous Graph Exploration, Deterministic Rendezvous with Detection Using Beeps, Deterministic network exploration by a single agent with Byzantine tokens, How much memory is needed for leader election, Derandomizing random walks in undirected graphs using locally fair exploration strategies, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, How to meet when you forget: log-space rendezvous in arbitrary graphs, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, Rendezvous in networks in spite of delay faults, Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences, Deterministic Symmetric Rendezvous in Arbitrary Graphs: Overcoming Anonymity, Failures and Uncertainty, Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal sequences for complete graphs
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Lower bounds on the length of universal traversal sequences
• Pseudorandom generators for space-bounded computation
• The electrical resistance of a graph captures its commute and cover times
• Universal traversal sequences for expander graphs
• On the cover time of random walks on graphs
• Lower bounds on universal traversal sequences based on chains of length five
• Pseudorandomness for network algorithms
• Bounds on Universal Sequences
• Universal traversal sequences for paths and cycles
• Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs