Mapping an unfriendly subway system

• Published in 2010
• Added on 2012-02-07

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

• https://link.springer.com/chapter/10.1007/978-3-642-13122-6_20
• http://people.scs.carleton.ca/~santoro/Reports/Subway.pdf

Other information

BibTeX entry

@article{Flocchini2010,
	key = {Flocchini2010},
	type = {article},
	title = {Mapping an unfriendly subway system},
	author = {Flocchini, Paola and Kellett, Matthew and Mason, P.},
	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 = {},
	date_added = {2012-02-07},
	date_published = {2010-10-09},
	urls = {https://link.springer.com/chapter/10.1007/978-3-642-13122-6{\_}20,http://people.scs.carleton.ca/{\~{}}santoro/Reports/Subway.pdf},
	collections = {Protocols and strategies},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-13122-6{\_}20 http://people.scs.carleton.ca/{\~{}}santoro/Reports/Subway.pdf},
	urldate = {2012-02-07},
	journal = {Fun with Algorithms},
	pages = {190--201},
	publisher = {Springer},
	year = 2010
}