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

20 Citations (Scopus)

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.
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
Pages127-139
Number of pages13
Publication statusPublished - 27 Sep 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

Conference

Conference12 International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005
CountryFrance
CityMont Saint-Michel
Period24/05/0526/05/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this