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

Stefan Dobrev, Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

19 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationStructural Information and Communication Complexity: 12th International Colloquium, SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings
EditorsAndrzej Pelc, Michel Raynal
Number of pages13
Publication statusPublished - 27 Sept 2005
Externally publishedYes
Event12 International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005 - Mont Saint-Michel, France
Duration: 24 May 200526 May 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
VolumeLNCS 3499
ISSN (Print)0302-9743


Conference12 International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005
CityMont Saint-Michel

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Finding short right-hand-on-the-wall walks in graphs'. Together they form a unique fingerprint.

Cite this