Abstrakt. Vi anser att en klass av mycket dynamiska nätverk modelleras på ett urbant tunnelbanesystem. Vi undersöker problemet med att skapa en karta över en sådan tunnelbana under mindre än idealiska förhållanden, där lokalbefolkningen inte är entusiastisk över processen och det finns en begränsad förmåga att kommunicera bland kartarna. Mer exakt studerar vi problemet med ett team av asynkrona beräkningsenheter (karteringsagenterna) som bestämmer placeringen av svarta hål i en mycket dynamisk graf, vars kanter definieras av de asynkrona rörelserna hos mobila enheter (tunnlar). Vi presenterar och analyserar ett lösningsprotokoll. Algoritmen löser problemet med minsta möjliga antal agenter. Vi fastställer också lägre gränser för antalet transportörer i värsta fall, vilket visar att vårt protokoll också är rörelseoptimalt.
Flocchini, Kellett, Mason och Santoro Ref har studerat kartläggningen av en PV-graf som innehåller svarta hål (siterförstörande medel).
Mapping an unfriendly subway system
{'venue': 'in Proc. 5th International Conference on Fun with Algorithms', 'journal': None, 'mag_field_of_study': ['Computer Science']}