Random Walks and Universal Traversal Sequences
The Problem
I have been working since 1996 on the problem of constructing universal traversal
sequences for undirected graphs. In 1988 (STOC88) I constructed in log space universal
traversal sequences of size O(n^4.76) for 2-regular graphs (constructive analogues
of 1-dimensional random walks). I have progressed since then towards the general
construction for arbitrary undirected graphs. Universal traversal sequences, provided
the deepest set of results in the area of graph connectivity and pseudorandom generators.
I am also investigating generalizations and characterizations of the results of
the type of Polya Random Walks Theorem.
Our STOC 1988 and FOCS 1990 Papers:
- S. Istrail, Constructing generalized universal traversal
sequences of polynomial size for graphs of small diameter,
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science
(FOCS90), IEEE Computer Society Press pp. 439-448, 1990
- S. Istrail, Polynomial universal traversal sequences for cycles are constructible, Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC88), ACM Press, pp. 491-453, 1988
