Abstrakt. Vi studerar problemet med prospektering av en mobil enhet (agent) av en klass av dynamiska nätverk, nämligen periodvis varierande grafer (PV-grafer, modellering av kollektivtrafiksystem, bland annat). Dessa definieras av en uppsättning av transportörer som följer oändligt deras föreskrivna rutt längs stationerna i nätet. Flocchini, Mans och Santoro [FMS09] (ISAAC 2009) studerade detta problem när agenten alltid måste resa på transportörerna och därför inte kan vänta på en station. De beskrev de nödvändiga och tillräckliga villkoren för att problemet ska kunna lösas och visade att det optimala antalet steg (och därmed rörelser) för att utforska en n-node PV-graf av k bärare och maximal period p är i  och k · p 2 ) i det allmänna fallet. I den här artikeln studerar vi effekten av förmågan att vänta på stationerna. Vi uppvisar de nödvändiga och tillräckliga förutsättningarna för att problemet ska kunna lösas i detta sammanhang, och vi bevisar att vänta på stationerna gör det möjligt för agenten att minska det värsta-fall optimal antal rörelser med en multiplikativ faktor på minst  på (p), medan tiden komplexiteten reduceras till  på (n · p). (I alla anslutna PV-graf, har vi n ≤ k · p.) Vi visar också några kompletterande optimala resultat i specifika fall (samma period för alla bärare, högt anslutna PV-grafer). Slutligen denna nya förmåga tillåter agenten att helt kartlägga PV-grafen, förutom att bara utforska den.
Effekterna av begränsad väntan i dynamiska nätverk har undersökts för prospektering REF.
On the power of waiting when exploring public transportation systems
{'venue': 'in Proc. of 15th Intl. Conf. On Principles Of Distributed Systems (OPODIS', 'journal': None, 'mag_field_of_study': ['Computer Science']}