Anonymous Graph Exploration with Binoculars - DIStributed Computing 2015 Access content directly
Conference Papers Year : 2015

Anonymous Graph Exploration with Binoculars

Abstract

We investigate the exploration of networks by a mobile agent. It is long known that, without global information about the graph, it is not possible to make the agent halts after the exploration except if the graph is a tree. We therefore endow the agent with binoculars, a sensing device that can show the local structure of the environment at a constant distance of the agent current location. We show that, with binoculars, it is possible to explore and halt in a large class of non-tree networks. We give a complete characterization of the class of networks that can be explored using binoculars using standard notions of discrete topology. This class is much larger than the class of trees: it contains in particular chordal graphs, plane triangulations and triangulations of the projective plane. Our characterization is constructive, we present an Exploration algorithm that is universal; this algorithm explores any network explorable with binoculars, and never halts in non-explorable networks.
Fichier principal
Vignette du fichier
08.pdf (456.92 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01206140 , version 1 (28-09-2015)

Identifiers

Cite

Jérémie Chalopin, Emmanuel Godard, Antoine Naudin. Anonymous Graph Exploration with Binoculars. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_8⟩. ⟨hal-01206140⟩
99 View
135 Download

Altmetric

Share

Gmail Facebook X LinkedIn More