TY - JOUR

T1 - On the exploration of time-varying networks

AU - Flocchini, Paola

AU - Mans, Bernard

AU - Santoro, Nicola

PY - 2013/1/21

Y1 - 2013/1/21

N2 - We study the computability and complexity of the exploration problem in a class of highly dynamic networks: carrier graphs, where the edges between sites exist only at some (unknown) times defined by the periodic movements of mobile carriers among the sites. 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 focus on the opportunistic exploration of these graphs, that is by an agent that exploits the movements of the carriers to move in the network. 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 carrier graphs defined by restricted classes of carrier movements. We then prove that the limitations on computability and complexity we have established are indeed tight. In fact we prove that all necessary conditions are also sufficient and all lower bounds on costs are tight. We do so constructively by presenting two optimal solution algorithms, one for anonymous systems, and one for those with distinct node IDs.

AB - We study the computability and complexity of the exploration problem in a class of highly dynamic networks: carrier graphs, where the edges between sites exist only at some (unknown) times defined by the periodic movements of mobile carriers among the sites. 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 focus on the opportunistic exploration of these graphs, that is by an agent that exploits the movements of the carriers to move in the network. 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 carrier graphs defined by restricted classes of carrier movements. We then prove that the limitations on computability and complexity we have established are indeed tight. In fact we prove that all necessary conditions are also sufficient and all lower bounds on costs are tight. We do so constructively by presenting two optimal solution algorithms, one for anonymous systems, and one for those with distinct node IDs.

UR - http://www.scopus.com/inward/record.url?scp=84871778432&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.10.029

DO - 10.1016/j.tcs.2012.10.029

M3 - Article

AN - SCOPUS:84871778432

VL - 469

SP - 53

EP - 68

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -