Interesting Esoterica

Mapping an unfriendly subway system

Article by Flocchini, Paola and Kellett, Matthew and Mason, P.
  • Published in 2010
  • Added on
In the collection
We consider a class of highly dynamic networks modelled on an urban subway system. We examine the problem of creating a map of such a subway in less than ideal conditions, where the local residents are not enthusiastic about the process and there is a limited ability to communicate amongst the mappers. More precisely, we study the problem of a team of asynchronous computational entities (the mapping agents) determining the location of black holes in a highly dynamic graph, whose edges are defined by the asynchronous movements ofmobile entities (the subway carriers). We present and analyze a solution protocol. The algorithm solves the problem with the minimum number of agents possible. We also establish lower bounds on the number of carrier moves in the worst case, showing that our protocol is also move-optimal.

Links

Other information

journal
Fun with Algorithms
pages
190--201
publisher
Springer

BibTeX entry

@article{Flocchini2010,
	title = {Mapping an unfriendly subway system},
	author = {Flocchini, Paola and Kellett, Matthew and Mason, P.},
	url = {http://www.springerlink.com/index/T0782U872653550H.pdf http://people.scs.carleton.ca/{\~{}}santoro/Reports/Subway.pdf},
	urldate = {2012-02-07},
	abstract = {We consider a class of highly dynamic networks modelled on an urban subway system. We examine the problem of creating a map of such a subway in less than ideal conditions, where the local residents are not enthusiastic about the process and there is a limited ability to communicate amongst the mappers. More precisely, we study the problem of a team of asynchronous computational entities (the mapping agents) determining the location of black holes in a highly dynamic graph, whose edges are defined by the asynchronous movements ofmobile entities (the subway carriers). We present and analyze a solution protocol. The algorithm solves the problem with the minimum number of agents possible. We also establish lower bounds on the number of carrier moves in the worst case, showing that our protocol is also move-optimal.},
	comment = {},
	journal = {Fun with Algorithms},
	pages = {190--201},
	publisher = {Springer},
	year = 2010,
	collections = {Protocols and strategies}
}