Exploration of Periodically Varying Graphs

Details Exploration of Periodically Varying Graphs Exploration of Periodically Varying Graphs

2009-09-24

arxiv.org/abs/0909.4369v1

Computer Science

Data Structures and Algorithms

22 pages. Shorter paper (10 pages) accepted at ISAAC 2009. ISAAC'09, The 20th International Symposium on Algorithms and Comput

Scientific paper

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. In fact we prove that all necessary conditions are also sufficient and all lower bounds on costs are tight. We do so constructively presenting two worst case optimal solution algorithms, one for anonymous systems, and one for those with distinct nodes ids. An added benefit is that the algorithms are rather simple.

Affiliated with

Also associated with

No associations

Rating

Exploration of Periodically Varying Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exploration of Periodically Varying Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploration of Periodically Varying Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424886