you're reading...

SACT seminar tomorrow 18-Nov-2009

Dear all,

Tomorrows SACT seminar will be given by our special guest
speaker Prof. Bernard Mans (http://www.comp.mq.edu.au/~bmans/).

Title: Exploration of Dynamic Graphs: the case of Periodically Varying Graphs

In this talk, we consider 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
algorithms, one for anonymous systems, and one for those with distinct
nodes ids. An added benefit is that the algorithms are rather simple.

This work is joint work with Paola Flocchini (Ottawa U.) and Nicola
Santoro (Carleton U.).

Time: Tomorrow (Thursday ) 11-12.
Venue: NICTA Seminar room at level 5 in the SIT building

The program for the SACT seminars can be found on:


NICTA | Locked Bag 9013 | Alexandria NSW 1435
T +61 02 8306 0758 | F +61 2 8306 0771 | M 0423 070 859



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: