Mostrar el registro sencillo del ítem

Setting port numbers for fast graph exploration

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
dc.date.accessioned2024-04-15T09:53:35Z
dc.date.available2024-04-15T09:53:35Z
dc.date.issued2008-07
dc.identifier.issn1879-2294
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198616
dc.description.abstractEnWe consider the problem of periodic graph exploration by a finite automaton in which an automaton with a constant number of states has to explore all unknown anonymous graphs of arbitrary size and arbitrary maximum degree. In anonymous graphs, nodes are not labeled but edges are labeled in a local manner (called {\em local orientation}) so that the automaton is able to distinguish them. Precisely, the edges incident to a node $v$ are given port numbers from $1$ to $d_v$, where $d_v$ is the degree of~$v$. Periodic graph exploration means visiting every node infinitely often. We are interested in the length of the period, i.e., the maximum number of edge traversals between two consecutive visits of any node by the automaton in the same state and entering the node by the same port. This problem is unsolvable if local orientations are set arbitrarily. Given this impossibility result, we address the following problem: what is the mimimum function $\pi(n)$ such that there exist an algorithm for setting the local orientation, and a finite automaton using it, such that the automaton explores all graphs of size $n$ within the period $\pi(n)$? The best result so far is the upper bound $\pi(n)\leq 10n$, by Dobrev et al. [SIROCCO 2005], using an automaton with no memory (i.e. only one state). In this paper we prove a better upper bound $\pi(n)\leq 4n$. Our automaton uses three states but performs periodic exploration independently of its starting position and initial state.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherElsevier
dc.subjectGraph exploration
dc.subjectmobile agent
dc.subjectrobot
dc.title.enSetting port numbers for fast graph exploration
dc.typeArticle de revue
dc.identifier.doi10.1016/j.tcs.2008.03.035
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalTheoretical Computer Science
bordeaux.page236-242
bordeaux.volume401
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue1-3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00341613
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00341613v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Theoretical%20Computer%20Science&rft.date=2008-07&rft.volume=401&rft.issue=1-3&rft.spage=236-242&rft.epage=236-242&rft.eissn=1879-2294&rft.issn=1879-2294&rft.au=ILCINKAS,%20David&rft.genre=article


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem