id: 06070194
dt: a
an: 06070194
au: Flocchini, Paola; Kellett, Matthew; Mason, Peter C.; Santoro, Nicola
ti: Finding good coffee in Paris.
so: Kranakis, Evangelos (ed.) et al., Fun with algorithms. 6th international
    conference, FUN 2012, Venice, Italy, June 4‒6, 2012. Proceedings.
    Berlin: Springer (ISBN 978-3-642-30346-3/pbk). Lecture Notes in
    Computer Science 7288, 154-165 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-30347-0_17
ab: Summary: Finding a good cup of coffee in Paris is difficult even among its
    world-renowned cafés, at least according to author David Downie
    (2011). We propose a solution that would allow tourists to create a map
    of the Paris Métro system from scratch that shows the locations of the
    cafés with the good coffee, while addressing the problem of the
    tourists losing interest in the process once they have found good
    coffee. We map the problem to the black hole search problem in the
    subway model introduced by Flocchini et al. at Fun with Algorithms
    2010. We provide a solution that allows the tourists to start anywhere
    and at any time, communicate using whiteboards on the subway trains,
    rely on much less information than is normally available to subway
    passengers, and work independently but collectively to map the subway
    network. Our solution is the first to deal with scattered agents
    searching for black holes in a dynamic network and is optimal both in
    terms of the team size and the number of carrier moves required to
    complete the map.
rv: