2003-41: On Traversal and Exploration Sequences

DIMACS TR: 2003-41

On Traversal and Exploration Sequences

Author: Michal Koucky

ABSTRACT Traversal sequences were defined in Aleliunas et al. (1979) as a tool for the study of undirected s-t-connectivity. Koucky (2001) defines a new variant of traversal sequences, exploration sequences, with certain advantages over the earlier notion of traversal sequences. An exact relationship of these two notions was not known.

In this paper we establish a relationship between these two concepts, in particular, we show that universal traversal sequences can be efficiently converted into universal exploration sequences. We also study conversion of universal exploration sequences for d-regular graphs into universal exploration sequences for d'-regular graphs. Further, we also show certain self-correcting properties of traversal and exploration sequences and we propose a candidate for a universal exploration sequence.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-41.ps.gz

DIMACS Home Page