Efficient periodic graph traversal on graphs with a given rotation system

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Luo, Xiao
We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The problem is to design an automaton A and a port labeling scheme L such that A (using L) performs on any undirected graph an infinite walk that periodically visit all vertices. The goal is to minimize the revisit time of any vertex over all graphs (traversal period) π. If the labeling scheme L is given by an adversary, it has been shown by Budach [6] that no such finite automaton A exists. If L does not need to be a permutation at every vertex, one can easily encode a spanning tree and A can perform traversal with period 2n − 2 even it is an oblivious agent. The problem is difficult when L is limited to be a permutation. The best known upper bound on the traversal period in such a case is 3.5n−2 by Czyzowicz et al. [11], where n is the number of vertices. It is an open problem whether it is possible to achieve traversal period of 2n − 2. In this thesis, we answer this question affirmatively under the assumption that the input graph G is given with a rotation system, where a rotation system, where a rotation system of a graph is given by lists of local orders of edges incident to each vertex the graph.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Thesis advisor: Manuch, Jan
Member of collection
Download file Size
etd19717.pdf 467.4 KB

Views & downloads - as of June 2023

Views: 7
Downloads: 1