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.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
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.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierDepartment of Algorithms and Systems Modelling [ETI GUT] [Gdansk University of Technology]
dc.contributor.authorKOSOWSKI, Adrian
dc.date.accessioned2024-04-15T09:51:48Z
dc.date.available2024-04-15T09:51:48Z
dc.date.issued2009-07
dc.date.conference2009-07
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198462
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 undirected counterparts 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.sponsorshipALgorithmique des Plates-formes A Grande Echelle - ANR-05-MMSA-0006
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 36th International Colloquium on Automata, Languages and Programming
dc.subjectgraph exploration : Propp machine
dc.title.enDerandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-02930-1_34
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.page411-422
bordeaux.volume5556
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleICALP 2009
bordeaux.countryGR
bordeaux.title.proceedingProceedings of the 36th International Colloquium on Automata, Languages and Programming
bordeaux.peerReviewedoui
hal.identifierhal-00374071
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00374071v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2036th%20International%20Colloquium%20on%20Automata,%20Languages%20and%20Programming&rft.date=2009-07&rft.volume=5556&rft.spage=411-422&rft.epage=411-422&rft.au=COOPER,%20Colin&ILCINKAS,%20David&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