Vorgehensweise bei Problemen mit dynamischen Graphen

Ich habe diese Frage bei generic stackoverflow gestellt und war hier gerichtet.

Es ist großartig, wenn jemand erklären kann, wie man partielle oder vollständig dynamische Graphprobleme im Allgemeinen angeht.

Beispielsweise:

• Finden Sie den kürzesten Pfad zwischen zwei Scheitelpunkten in einem ungerichteten gewichteten Diagramm für Instanzen, wenn bei jeder Instanz eine Kante entfernt wird.$(u,v)$$n$
• Finden Sie die Anzahl der verbundenen Komponenten in einem ungerichteten Diagramm für n Instanzen, wenn bei jeder Instanz eine Kante entfernt wird usw.

Ich bin kürzlich in einem Programmierwettbewerb auf dieses Problemgenre gestoßen. Ich habe im Internet gesucht und zahlreiche Forschungsarbeiten zu dynamischen Graphen gefunden [1,2]. Ich habe ein paar von ihnen gelesen und konnte nichts direktes finden (Clustering, Sparsification usw.). Tut mir leid, dass ich vage bin.

Ich weiß es wirklich zu schätzen, wenn einige Hinweise geben können, um diese Konzepte besser zu verstehen.

1. Dynamische Graph-Algorithmen von D. Eppstein, Z. Galil, GF Italiano (1999)
2. Kürzeste Wege auf dynamischen Graphen von G. Nannicini, L. Liberti (2008)

Es ist schwierig, Ihnen konkrete Techniken zu vermitteln, da "dynamisch" eine Vielzahl von Dingen bedeuten kann und die Algorithmen / Ergebnisse von Ihrem Modell abhängen. Nachfolgend finden Sie eine Übersicht der Bedenken. Hier ist ein Artikel, der einen Überblick über verschiedene Anliegen und Modelle gibt (im Zusammenhang mit dem, was Peter in einer anderen Antwort zitiert hat).

Bei dynamischen Problemen im Allgemeinen sind die Hauptprobleme:

• Wollen Sie auf jeden Fall eine exakte Lösung, oder ist eine Annäherung zulässig?
• Wissen Sie etwas darüber, welche Veränderungen eintreten werden (z. B. eine Wahrscheinlichkeitsverteilung), oder sind sie alle gleich wahrscheinlich?
• Wie erfährt der Algorithmus von den Änderungen?

Ein typisches dynamisches Modell sieht folgendermaßen aus:

1. Bei einem gegebenen Diagramm möchten Sie eine Eigenschaft berechnen. Sie dürfen eine Lösung für das ursprüngliche Diagramm berechnen.

2. Ihnen wird dann eine Änderung mitgeteilt: Kante wird gelöscht. Berechnen Sie die Eigenschaft im neuen Diagramm mit begrenzten Ressourcen .$(e,f)$

3. Wiederholen Sie 2 für mal.$n$

Und hier sind 3 mögliche Modifikationen:

• Sie dürfen zu Beginn nicht die vollständige Lösung berechnen, da die Informationen, die Zeit und der Raum begrenzt sind (ein Beispiel hierfür sind Online-Algorithmen ).

• In Schritt 2 wird der Algorithmus nicht „ sagt“ die Modifikation, hat aber zu finden , die Änderung in der graphischen Darstellung durch eine Datenstruktur oder etwas abfragt.

• Ein verteiltes Modell (wie Peter in einer anderen Antwort erläutert), in dem die Informationen lokal ermittelt und die Berechnung / Änderungen lokal vorgenommen werden.

Dynamische Modelle sind in der Regel aufgrund von Ressourcenbeschränkungen (z. B. Zeit / Raum) interessant. Wenn ich in Schritt 2 eine vollständige Antwort berechnen durfte (wie in Schritt 1), ist das Problem einfach, da es sich nur um ein wiederholtes statisches Diagrammproblem handelt. Wir sind mehr an der kleinsten Menge an Ressourcen interessiert, die zur Berechnung der Änderung erforderlich sind.

Dynamische Graphenmodelle wurden im Distributed Computing intensiv untersucht. Für verteilte Algorithmen ist die Berechnung in Runden strukturiert, und die Topologie von Graphen (= Netzwerk) kann sich von Runde zu Runde ändern, die von einem Gegner gesteuert werden. Darüber hinaus führt jeder Knoten des Graphen einen Algorithmus aus, der eine Nachricht an seine (aktuellen!) Nachbarn senden kann. (Diese Nachricht ist die Eingabe des Algorithmus des Nachbarn in der nächsten Runde.) Interessant ist, dass ein Knoten nicht den gesamten Graphen "sieht", sondern nur seine lokale Umgebung.

Probleme, die in diesen Einstellungen berücksichtigt werden, sind beispielsweise Informationen, bei denen jeder Knoten im Diagramm anfänglich ein Token enthält, und schließlich möchten Sie, dass jeder Knoten jedes Token gesehen hat. Das Ziel besteht darin, Algorithmen zu entwerfen, die dies in der geringsten Anzahl von Runden unter Verwendung der geringsten Anzahl von Nachrichten erreichen. Siehe [2] für eine aktuelle Umfrage.

Für die nicht verteilte Einstellung sollten Sie sich [1] ansehen, eine Erweiterung des Papiers, das Sie erwähnt haben.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal und Fabio Vandin: Algorithmen zur Entwicklung von Graphen . ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Dynamische Netzwerke: Modelle und Algorithmen . SIGACT News 42 (1): 82-96 (2011)

Aufbauend auf @ Peter-Antworten (es ist ein sehr langer Kommentar, daher habe ich ihn nur als Antwort eingefügt, damit jemand davon profitiert).

Ich würde den folgenden Verweis vorschlagen:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Zeitvariable Graphen und dynamische Netzwerke. IJPEDS 27 (5): 387-408 (2012)

$\Delta$

Was bei dieser Klassifizierung wirklich wichtig ist, ist, dass es Einschlussbeziehungen zwischen den verschiedenen Klassen gibt. Wenn Sie also ein Problem in einer bestimmten Klasse lösen, lösen Sie es in jeder anderen Klasse, in der es enthalten ist.

Dieselben Autoren stellten Rundfunkalgorithmen für einige der genannten Diagramme vor. Sie gaben verschiedene Leistungsmetriken in Bezug auf die Zeit an (dh unterschiedliche Definition der kürzesten Zeit). Beim Broadcasting besteht die Idee darin, dass jeder Knoten eine Ansicht des Netzwerks in der Zeitdomäne erstellt. Dies geschieht durch wiederholtes Abhören von Nachbarn und Senden von Informationen an Nachbarn. Wenn Periodizität angenommen wird, kann ein Knoten den kürzesten Zeitpfad zu einem anderen Knoten angeben. Diese Informationen werden beim Routing verwendet. Weitere Details finden Sie in:

Arnaud Casteigts, Bernard Mans, Nicola Santoro, Paola Flocchini: Deterministische Berechnungen in zeitveränderlichen Graphen: Rundfunk unter unstrukturierter Mobilität. IFIP TCS 2010: 111-124

$u$$v$$\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$$u$$v$$v$$u$

Ich habe einen Vortrag der Vorgänger besucht. Nach meinem Verständnis behaupten sie, dass wir nicht in der Lage sind, mit dynamischen Graph-Algorithmen umzugehen (gemäß den Definitionen, die sie befolgen). Das sind wir noch bei einfachen Klassen. Tatsächlich behaupten sie, dass die meisten Algorithmen für mobile Computer einfach davon ausgehen, dass ihre Algorithmen zu schnell sind, um ausgeführt zu werden, während sich das Netzwerk im Übergang befindet! (was ich glaube, dass ich viel gehört habe) - Oder nehmen Sie einfach die Periodizität der Kantenerscheinung an (siehe verzögerungstolerante Netzwerke usw.)