Impact of memory size on graph exploration capability
| hal.structure.identifier | Laboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA] | |
| dc.contributor.author | FRAIGNIAUD, Pierre | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | ILCINKAS, David | |
| hal.structure.identifier | Département d'Informatique et d'Ingénierie [DII] | |
| dc.contributor.author | PELC, Andrzej | |
| dc.date.accessioned | 2024-04-15T09:53:37Z | |
| dc.date.available | 2024-04-15T09:53:37Z | |
| dc.date.issued | 2008-06 | |
| dc.identifier.issn | 0166-218X | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198618 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | Graph exploration | |
| dc.subject.en | finite automaton | |
| dc.subject.en | memory size | |
| dc.subject.en | mobile agent | |
| dc.subject.en | robot | |
| dc.title.en | Impact of memory size on graph exploration capability | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.dam.2007.11.001 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.journal | Discrete Applied Mathematics | |
| bordeaux.page | 2310-2319 | |
| bordeaux.volume | 156 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 12 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00341600 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00341600v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Applied%20Mathematics&rft.date=2008-06&rft.volume=156&rft.issue=12&rft.spage=2310-2319&rft.epage=2310-2319&rft.eissn=0166-218X&rft.issn=0166-218X&rft.au=FRAIGNIAUD,%20Pierre&ILCINKAS,%20David&PELC,%20Andrzej&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||