Please use this identifier to cite or link to this item:
|Title:||Finding short right-hand-on-the-wall walks in graphs|
|Citation:||Dobrev, S.,Jansson, J.,Sadakane, K.,Sung, W.-K. (2005). Finding short right-hand-on-the-wall walks in graphs. Lecture Notes in Computer Science 3499 : 127-139. ScholarBank@NUS Repository.|
|Abstract:||We consider the problem of perpetual traversal by a single agent in an anonymous undirected graph G. Our requirements are: (1) deterministic algorithm, (2) each node is visited within O(n) moves, (3) the agent uses no memory, it can use only the label of the link via which it arrived to the current node, (4) no marking of the underlying graph is allowed and (5) no additional information is stored in the graph (e.g. routing tables, spanning tree) except the ability to distinguish between the incident edges (called Local Orientation). This problem is unsolvable, as has been proven in [9, 28] even for much less restrictive setting. Our approach is to somewhat relax the requirement (5). We fix the following traversal algorithm: "Start by taking the edge with the smallest label. Afterwards, whenever you come to a node, continue by taking the successor edge (in the local orientation) to the edge via which you arrived" and ask whether it is for every undirected graph possible to assign the local orientations in such a way that the resulting perpetual traversal visits every node in O(n) moves. We give a positive answer to this question, by showing how to construct such local orientations. This leads to an extremely simple, memoryless, yet efficient traversal algorithm. © Springer-Verlag Berlin Heidelberg 2005.|
|Source Title:||Lecture Notes in Computer Science|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 8, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.