Show simple item record

On the Power of Waiting when Exploring Public Transportation Systems

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.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorWADE, Ahmed
dc.date.accessioned2024-04-15T09:45:52Z
dc.date.available2024-04-15T09:45:52Z
dc.date.issued2011
dc.date.conference2011-12-13
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197957
dc.description.abstractEnWe study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a n-node PV-graph of k carriers and maximal period p is in Theta(k p^2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least Theta(p), while the time complexity is reduced to Theta(n p). (In any connected PV-graph, we have n < k p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 15th International Conference On Principles Of Distributed Systems
dc.subjectExploration
dc.subjectDynamic graphs
dc.subjectMobile agent
dc.subjectPV-graph
dc.title.enOn the Power of Waiting when Exploring Public Transportation Systems
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-25873-2_31
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page451-464
bordeaux.volume7109
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleOPODIS 2011
bordeaux.countryFR
bordeaux.title.proceedingProceedings of the 15th International Conference On Principles Of Distributed Systems
bordeaux.conference.cityToulouse
bordeaux.peerReviewedoui
hal.identifierhal-00656607
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2011-12-16
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00656607v1
bordeaux.COinSctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.btitle=Proceedings%20of%20the%2015th%20International%20Conference%20On%20Principles%20Of%20Distributed%20Systems&amp;rft.date=2011&amp;rft.volume=7109&amp;rft.spage=451-464&amp;rft.epage=451-464&amp;rft.au=ILCINKAS,%20David&amp;WADE,%20Ahmed&amp;rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record