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.date.accessioned2024-04-15T09:43:40Z
dc.date.available2024-04-15T09:43:40Z
dc.date.issued2013
dc.date.conference2013
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197786
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. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of 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$. We also obtain almost-tight bounds on the asymptotic relation between exploration time and team size, for large $k$. 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. This shows a clear separation between the global and local communication models.
dc.language.isoen
dc.publisherSpringer
dc.title.enFast Collaborative Graph Exploration
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-39212-2_46
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page520-532
bordeaux.volume7966
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleICALP - 40th International Colloquium on Automata, Languages and Programming
bordeaux.countryLV
bordeaux.conference.cityRiga
bordeaux.peerReviewedoui
hal.identifierhal-00802308
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00802308v1
bordeaux.COinSctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.date=2013&amp;rft.volume=7966&amp;rft.spage=520-532&amp;rft.epage=520-532&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