Impact of memory size on graph exploration capability

Pierre Fraigniaud (1) , David Ilcinkas (2, 3) , Andrzej Pelc (4)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
4 DII - Département d'Informatique et d'Ingénierie

A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs.

Mots clés: Graph exploration; finite automaton; memory size; mobile agent; robot

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc. Impact of memory size on graph exploration capability. Discrete Applied Mathematics, 2008, 156 (12), pp.2310-2319. ⟨10.1016/j.dam.2007.11.001⟩. ⟨hal-00341600⟩