Universal traversal sequences for expander graphs

DOI10.1016/0020-0190(93)90199-JzbMath0770.68069OpenAlexW2040188343MaRDI QIDQ1802060

Avi Wigderson, Shlomo Hoory

Publication date: 8 August 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90199-j

zbMATH Keywords

connectivityexpander graphsexplicit constructionspace-bounded computationuniversal traversal sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Universal traversal sequences with backtracking. ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). ⋮ Impact of memory size on graph exploration capability ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Graph exploration by a finite automaton

Cites Work

• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Explicit constructions of linear-sized superconcentrators
• Relationships between nondeterministic and deterministic tape complexities
• Two Applications of Inductive Counting for Complementation Problems

This page was built for publication: Universal traversal sequences for expander graphs