Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/147984
4 Visitors
6 Hits
1 Downloads
- Title
- Exploration of periodically varying graphs
- Related
- International Symposium on Algorithms and Computation (20th : 2009) (16 - 18 December 2009 : Honolulu)
- Related
- Dong, Yingfei; Du, Ding-Zhu and Ibarra, Oscar. Algorithms and computation : 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009 : proceedings, p.534-543
- DOI
- 10.1007/978-3-642-10631-6_55
- Related
- Lecture notes in computer science 5878
- Publisher
- Berlin ; New York : Springer-Verlag
- Date
- 2009
- FoR/RFCD Code(s)
-
080201 Analysis of Algorithms and Complexity
- Author/Creator
- Flocchini, Paola
- Author/Creator
- Mans, Bernard
- Author/Creator
- Santoro, Nicola
- Description
- 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.
- Description
- 10 page(s)
- Subject Keyword
- 080201 Analysis of Algorithms and Complexity
- Resource Type
- conference paper
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/147984
- Identifier
- ISBN:9783642106309
- Identifier
- ISSN:0302-9743
- Identifier
- mq-rm-2009005534
- Language
- eng
- Reviewed
