Exploration of periodically varying graphs

Paola Flocchini*, Bernard Mans, Nicola Santoro

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

24 Citations (Scopus)

Abstract

We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined by the periodic movements of carriers. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards' tours, etc. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the PV graphs defined by restricted classes of carriers movements: simple routes, and circular routes. We then prove that the limitations on computability and complexity we have established are indeed tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
EditorsYingfei Dong, Ding-Zhu Du, Oscar Ibarra
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages534-543
Number of pages10
Volume5878 LNCS
ISBN (Electronic)9783642106316
ISBN (Print)3642106307, 9783642106309
DOIs
Publication statusPublished - 2009
Event20th International Symposium on Algorithms and Computation, ISAAC - 2009 - Honolulu, United States
Duration: 16 Dec 200918 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5878 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other20th International Symposium on Algorithms and Computation, ISAAC - 2009
CountryUnited States
CityHonolulu
Period16/12/0918/12/09

Fingerprint Dive into the research topics of 'Exploration of periodically varying graphs'. Together they form a unique fingerprint.

  • Cite this

    Flocchini, P., Mans, B., & Santoro, N. (2009). Exploration of periodically varying graphs. In Y. Dong, D-Z. Du, & O. Ibarra (Eds.), Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings (Vol. 5878 LNCS, pp. 534-543). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS). Berlin; Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-10631-6_55