Universal traversal sequences for expander graphs
We give an explicit construction of a polynomial length universal sequence for a class of constant degree expander graphs. The extra requirements is that the labeling of the edges be consistent, i.e. that for each vertex not only the outgoing labels be distinct, but the incoming labels as well. Consistent labeling is an intermediate requirement between the weaker unrestricted labeling and the stronge requirement of symmetric labeling (where both labels on each edge are identical). For any of them, obtaining universal traversal sequences in uniform logspace will put undirected reachability in DSPACE\((\log n)\). For expanders we do not know how to handle unrestricted labeling, while the symmetric case is trivial (since the diameter is small). Here we handle the intermediate case of consistent labeling. Our construction is based on ideas from the universal sequence for cliques constructed in [\textit{H. J. Karloff, R. Paturi} and \textit{J. Simon}, Universal traversal sequences of length \(n^{O(\log n))}\) for cliques, Inform. Process. Lett. 28, 241-243 (1988; Zbl 0667.68078)].
- 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
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Explicit constructions of linear-sized superconcentrators
- Relationships between nondeterministic and deterministic tape complexities
- Two Applications of Inductive Counting for Complementation Problems
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Universal traversal sequences with backtracking.
- Graph exploration by a finite automaton
- scientific article; zbMATH DE number 3911721 (Why is no real title available?)
- Universal traversal sequences for paths and cycles
- scientific article; zbMATH DE number 1796948 (Why is no real title available?)
- Expanders Are Universal for the Class of All Spanning Trees
- Memory Efficient Anonymous Graph Exploration
- Graph Traversals as Universal Constructions
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
- Pseudorandom generators for unbounded-width permutation branching programs
- Universal sequences of spatial graphs
- Impact of memory size on graph exploration capability
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)
