Afficher la notice abrégée

Collision-Free Network Exploration

hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorDERENIOWSKI, Dariusz
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorGASIENIEC, Leszek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierNetworks, Graphs and Algorithms [GANG]
hal.structure.identifierLaboratoire d'informatique Algorithmique : Fondements et Applications [LIAFA]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorPAJAK, Dominik
dc.date.accessioned2024-04-15T09:44:33Z
dc.date.available2024-04-15T09:44:33Z
dc.date.issued2014-03-31
dc.date.conference2014-03-31
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197856
dc.description.abstractEnA set of mobile agents is placed at different nodes of a $n$-node network. The agents synchronously move along the network edges in a {\em collision-free} way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible time required to complete the collision-free {\em network exploration}, i.e., to reach a configuration in which each agent is guaranteed to have visited all network nodes and has returned to its starting location. We first consider the scenario when each mobile agent knows the map of the network, as well as its own initial position. We establish a connection between the number of rounds required for collision-free exploration and the degree of the minimum-degree spanning tree of the graph. We provide tight (up to a constant factor) lower and upper bounds on the collision-free exploration time in general graphs, and the exact value of this parameter for trees. For our second scenario, in which the network is unknown to the agents, we propose collision-free exploration strategies running in $O(n^2)$ rounds for tree networks and in $O(n^5\log n)$ rounds for general networks.
dc.description.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.publisherSpringer
dc.title.enCollision-Free Network Exploration
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-54423-1_30
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page342-354
bordeaux.volume8392
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleLATIN - 11th Latin American Theoretical INformatics Symposium
bordeaux.countryUY
bordeaux.conference.cityMontevideo
bordeaux.peerReviewedoui
hal.identifierhal-00736276
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2014-04-04
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00736276v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2014-03-31&rft.volume=8392&rft.spage=342-354&rft.epage=342-354&rft.au=CZYZOWICZ,%20Jurek&DERENIOWSKI,%20Dariusz&GASIENIEC,%20Leszek&KLASING,%20Ralf&KOSOWSKI,%20Adrian&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée