TY - GEN

T1 - Finding short right-hand-on-the-wall walks in graphs

AU - Dobrev, Stefan

AU - Jansson, Jesper Andreas

AU - Sadakane, Kunihiko

AU - Sung, Wing Kin

PY - 2005/9/27

Y1 - 2005/9/27

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=24944433884&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

T3 - Lecture Notes in Computer Science

SP - 127

EP - 139

BT - Structural Information and Communication Complexity: 12th International Colloquium, SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings

A2 - Pelc, Andrzej

A2 - Raynal, Michel

T2 - 12 International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005

Y2 - 24 May 2005 through 26 May 2005

ER -