Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Theoretical Computer Science - Stefan Dobrev (19.5.2017)

Friday 19.5.2017 at 11:00, Lecture room M/213


16. 05. 2017 13.01 hod.
By: Rastislav Kralovič

Stefan Dobrev:
Efficient Periodic Traversal on Graphs with Given Rotation Systems

Abstract: 
We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The nodes are anonymous, but the ports in each node have unique (within the node) labels. The problem is to design an automaton A and a port re-labeling scheme L such that A performs on L(G) an infinite walk w, periodically visiting all nodes. The goal is to minimize the revisit time (traversal period) pi of w.
If L cannot change the input labels, it has been shown by Budach that the problem is unsolvable. If L can in node v use deg(v)+1 labels, it can encode a spanning tree and traversal with period 2n-2 is trivial even with an oblivious agent. The problem is interesting when L is limited to be a permutation.
The best known upper bound on the traversal period in such case is 3.5n - 2 by Czyzowicz et al., where n is the number of nodes of G. It is an open problem whether it is possible to achieve traversal period 2n-2.
In this paper, we answer this question affirmatively under the assumption that that the input graph G is given with a rotation system. A rotation system of a graph is a combinatorial encoding of graph's embedding into an orientable surface. This encoding can be described by specifying a circular ordering of edges around each node.
While this is clearly an additional information, it appears to be barely sufficient to solve the problem with the optimal period 2n-2: Several aspects of the construction need to fit 'just right' to solve all the technical issues, especially in graphs with small maximal degree (3 or 4). 

web:  http://kedrigern.dcs.fmph.uniba.sk/STI2 
rss:  http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php