Universal traversal sequences for expander graphs
DOI10.1016/0020-0190(93)90199-JzbMATH Open0770.68069OpenAlexW2040188343MaRDI QIDQ1802060FDOQ1802060
Authors: Shlomo Hoory, A. Wigderson 
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
Recommendations
- scientific article; zbMATH DE number 3911721
- Universal traversal sequences for paths and cycles
- Universal Traversal Sequences
- Universal sequences for complete graphs
- Graph Traversals as Universal Constructions
- scientific article; zbMATH DE number 1248188
- Universal sequences of spatial graphs
- Lower bounds on the length of universal traversal sequences
- Universal traversal sequences with backtracking.
- Expander graphs and their applications
connectivityexpander graphsexplicit constructionspace-bounded computationuniversal traversal sequences
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)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Explicit constructions of linear-sized superconcentrators
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Two Applications of Inductive Counting for Complementation Problems
Cited In (12)
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Expanders Are Universal for the Class of All Spanning Trees
- Title not available (Why is that?)
- Memory Efficient Anonymous Graph Exploration
- Graph Traversals as Universal Constructions
- Universal sequences of spatial graphs
- Universal traversal sequences with backtracking.
- Universal traversal sequences for paths and cycles
- Graph exploration by a finite automaton
- Impact of memory size on graph exploration capability
- Title not available (Why is that?)
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
This page was built for publication: Universal traversal sequences for expander graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1802060)
