Afficher la notice abrégée

Derandomizing random walks in undirected graphs using locally fair exploration strategies

hal.structure.identifierDepartment of Computer Science [DCS]
dc.contributor.authorCOOPER, Colin
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorILCINKAS, David
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorKLASING, Ralf
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorKOSOWSKI, Adrian
dc.date.accessioned2024-04-15T09:46:44Z
dc.date.available2024-04-15T09:46:44Z
dc.date.created2009
dc.date.issued2011
dc.identifier.issn0178-2770
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198035
dc.description.abstractEnWe consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Verlag
dc.subject.enRandom walk
dc.subject.enGraph exploration
dc.title.enDerandomizing random walks in undirected graphs using locally fair exploration strategies
dc.typeArticle de revue
dc.identifier.doi10.1007/s00446-011-0138-4
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.journalDistributed Computing
bordeaux.page91-99
bordeaux.volume24
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00638229
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00638229v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Distributed%20Computing&rft.date=2011&rft.volume=24&rft.issue=2&rft.spage=91-99&rft.epage=91-99&rft.eissn=0178-2770&rft.issn=0178-2770&rft.au=COOPER,%20Colin&ILCINKAS,%20David&KLASING,%20Ralf&KOSOWSKI,%20Adrian&rft.genre=article


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