Afficher la notice abrégée

Fast Collaborative Graph Exploration

hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorDERENIOWSKI, Dariusz
hal.structure.identifierInstitut für Mathematik [Berlin]
dc.contributor.authorDISSER, Yann
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
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorUZNANSKI, Przemyslaw
dc.contributor.editorNisse
dc.contributor.editorNicolas and Rousseau
dc.contributor.editorFranck and Busnel
dc.contributor.editorYann
dc.date.accessioned2024-04-15T09:43:26Z
dc.date.available2024-04-15T09:43:26Z
dc.date.issued2013-05-05
dc.date.conference2013-05-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197766
dc.description.abstractEnWe study the following scenario of online graph exploration. A team of $k$ agents is initially located at a distinguished vertex $r$ of an undirected graph. In each time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains a list of the identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure that every vertex has been visited by some agent. We consider two communication models: one in which all agents have global knowledge of the state of the exploration, and one in which agents may only exchange information when simultaneously located at the same vertex. As our main result, we provide the first strategy which performs exploration of a graph with $n$ vertices at a distance of at most $D$ from $r$ in time $O(D)$, using a team of agents of polynomial size $k = D n^{1+ \epsilon} < n^{2+\epsilon}$, for any $\epsilon > 0$. Our strategy works in the local communication model, without knowledge of global parameters such as $n$ or $D$. For any constant $c>1$, we show that in the global communication model, a team of $k = D n^c$ agents can always complete exploration in $D(1+ \frac{1}{c-1} +o(1))$ time steps, whereas at least $D(1+ \frac{1}{c} -o(1))$ steps are sometimes required. In the local communication model, $D(1+ \frac{2}{c-1} +o(1))$ steps always suffice to complete exploration, and at least $D(1+ \frac{2}{c} -o(1))$ steps are sometimes required.
dc.language.isoen
dc.source.title15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
dc.title.enFast Collaborative Graph Exploration
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page1-4
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
bordeaux.countryFR
bordeaux.title.proceeding15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel)
bordeaux.peerReviewedoui
hal.identifierhal-00818451
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00818451v1
bordeaux.COinSctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.btitle=15%C3%A8mes%20Rencontres%20Francophones%20sur%20les%20Aspects%20Algorithmiques%20des%20T%C3%A9l%C3%A9communications%20(AlgoTel)&amp;rft.date=2013-05-05&amp;rft.spage=1-4&amp;rft.epage=1-4&amp;rft.au=DERENIOWSKI,%20Dariusz&amp;DISSER,%20Yann&amp;KOSOWSKI,%20Adrian&amp;PAJAK,%20Dominik&amp;UZNANSKI,%20Przemyslaw&amp;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