TY - GEN
T1 - Exploration of periodically varying graphs
AU - Flocchini, Paola
AU - Mans, Bernard
AU - Santoro, Nicola
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=75749108912&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10631-6_55
DO - 10.1007/978-3-642-10631-6_55
M3 - Conference proceeding contribution
AN - SCOPUS:75749108912
SN - 3642106307
SN - 9783642106309
VL - 5878 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 534
EP - 543
BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
A2 - Dong, Yingfei
A2 - Du, Ding-Zhu
A2 - Ibarra, Oscar
PB - Springer, Springer Nature
CY - Berlin; Heidelberg
T2 - 20th International Symposium on Algorithms and Computation, ISAAC - 2009
Y2 - 16 December 2009 through 18 December 2009
ER -