Universal traversal sequences with backtracking.

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

Michal Koucký

Publication date: 14 May 2003

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

Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00023-5

zbMATH Keywords

exploration sequences

Mathematics Subject Classification ID

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

Related Items (14)

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

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

This page was built for publication: Universal traversal sequences with backtracking.