Back to Search
Start Over
On the Power of Waiting When Exploring Public Transportation Systems
- Source :
- Lecture Notes in Computer Science ISBN: 9783642258725, OPODIS, Proceedings of the 15th International Conference On Principles Of Distributed Systems, OPODIS 2011, OPODIS 2011, Dec 2011, Toulouse, France. pp.451-464, ⟨10.1007/978-3-642-25873-2_31⟩
- Publication Year :
- 2011
- Publisher :
- Springer Berlin Heidelberg, 2011.
-
Abstract
- International audience; We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a n-node PV-graph of k carriers and maximal period p is in Theta(k p^2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least Theta(p), while the time complexity is reduced to Theta(n p). (In any connected PV-graph, we have n < k p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.
- Subjects :
- Mobile agent
Discrete mathematics
PV-graph
Class (set theory)
Computer science
business.industry
Distributed computing
Multiplicative function
Context (language use)
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Power (physics)
Set (abstract data type)
010201 computation theory & mathematics
Public transport
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Exploration
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
business
Time complexity
Dynamic graphs
Subjects
Details
- ISBN :
- 978-3-642-25872-5
- ISBNs :
- 9783642258725
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science ISBN: 9783642258725, OPODIS, Proceedings of the 15th International Conference On Principles Of Distributed Systems, OPODIS 2011, OPODIS 2011, Dec 2011, Toulouse, France. pp.451-464, ⟨10.1007/978-3-642-25873-2_31⟩
- Accession number :
- edsair.doi.dedup.....fc1a5ba3d3df168b0c43a8c84910e5cd