Afficher la notice abrégée

Bounds on the Cover Time of Parallel Rotor Walks

hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorDERENIOWSKI, Dariusz
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
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:42:55Z
dc.date.available2024-04-15T09:42:55Z
dc.date.created2013-09-20
dc.date.issued2014-03-05
dc.date.conference2014-03-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197720
dc.description.abstractEnThe \emph{rotor-router mechanism} was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of $k$ identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in round-robin fashion, according to the fixed ordering. We consider the \emph{cover time} of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the starting locations of the walks. In the case of $k=1$, Yanovski et al.\ (2003) and Bampas et al.\ (2009) showed that a single walk achieves a cover time of exactly $\Theta(m D)$ for any $n$-node graph with $m$ edges and diameter $D$, and that the walker eventually stabilizes to a traversal of an Eulerian circuit on the set of all directed edges of the graph. For $k>1$ parallel walks, no similar structural behaviour can be observed. In this work we provide tight bounds on the cover time of $k$ parallel rotor walks in a graph. We show that this cover time is at most $\Theta (m D / \log k)$ and at least $\Theta (m D / k)$ for any graph, which corresponds to a speedup of between $\Theta(\log k)$ and $\Theta(k)$ with respect to the cover time of a single walk. Both of these extremal values of speedup are achieved for some graph classes. Our results hold for up to a polynomially large number of walks, $k = O(poly(n))$.
dc.description.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.subject.enDistributed graph exploration Rotor-Router Cover time Collaborative robots Parallel random walks Derandomization
dc.title.enBounds on the Cover Time of Parallel Rotor Walks
dc.typeCommunication dans un congrès
dc.identifier.doi10.4230/LIPIcs.STACS.2014.263
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page263--275
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSTACS 2014
bordeaux.countryFR
bordeaux.conference.cityLyon
bordeaux.peerReviewedoui
hal.identifierhal-00865065
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00865065v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2014-03-05&rft.spage=263--275&rft.epage=263--275&rft.au=DERENIOWSKI,%20Dariusz&KOSOWSKI,%20Adrian&PAJAK,%20Dominik&UZNANSKI,%20Przemyslaw&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