# Mapping an unfriendly subway system

• Published in 2010
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.

## Other information

key
Flocchini2010
type
article
2012-02-07
date_published
2010-09-14
journal
Fun with Algorithms
pages
190--201
publisher
Springer

### 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 = {},
}