Mischen von Token in einem Diagramm mithilfe lokaler Swaps

Sei ein nicht regulär verbundener Graph, dessen Grad begrenzt ist. Angenommen, jeder Knoten enthält ein eindeutiges Token. $G= (V, E)$

Ich möchte die Token innerhalb des Diagramms gleichmäßig mischen, indem ich nur lokale Swaps verwende (dh den Austausch der Token zwischen zwei benachbarten Knoten). Ist für dieses Problem eine Untergrenze bekannt?

Die einzige Idee, die ich hatte, war, ein zufälliges Laufergebnis zu verwenden und dann zu sehen, wie viele Swaps ich brauche, um den Effekt von zufälligen Spaziergängen, die Token in der Grafik transportieren, zu "simulieren".

ds.algorithms random-walks dc.distributed-comp Sylvain Peyronnet
quelle

Welche Art von Untergrenze suchen Sie? Gesamtzahl der Swaps? Anzahl der parallelen Runden (dh in 1 Schritt können Sie entlang aller Kanten eines Matchings in

tauschen )? Untergrenze als Funktion von

? Kennen alle Knoten die Topologie von

(und können ihr Verhalten entsprechend anpassen), oder suchen Sie nach einer festen Strategie, die Sie in jedem Diagramm anwenden können?

G

$G$

| V |

$|V|$

d i a m (G)

$diam(G)$

G

$G$

Jukka Suomela

Ich hätte genauer sein sollen, sorry. Ziel ist es, eine Datenverbreitungsmethode für Sensornetzwerke zu entwickeln, die Probleme mit auf zufälligen Spaziergängen basierenden Methoden vermeidet (im Wesentlichen Informationsverlust aufgrund der Kollision mehrerer Token am selben Knoten). Ich interessiere mich also für die Gesamtzahl der Swaps (dies gibt die Anzahl der im Netzwerk zirkulierenden Nachrichten an) und die Anzahl der Runden (um eine grobe Schätzung der Konvergenzzeit zu erhalten). Ein LB als Funktion von

ist in Ordnung und Knoten sind (leider) nicht topologiebewusst.

V

$V$

Sylvain Peyronnet

Antworten:

Angenommen, Ihr Diagramm war ein Pfad. Ich denke, dann wird dieses Problem gleichbedeutend mit dem Sortieren einer zufälligen Folge von Zahlen in einem Array durch Vertauschen benachbarter Einträge. Selbst wenn alle Knoten topologiebewusst sind, erhalten Sie eine ^ 2-Untergrenze für die Anzahl der Swaps (kann nicht besser sein als die Blasensortierung, die selbst bei einer zufälligen Eingabe n ^ 2 ist).

Lev Reyzin
quelle

O (n^{2})

$O(n^2)$

Diese LB sagt, dass Sie den Algorithmus nicht verbessern können, selbst wenn Sie Ihre Swaps auswählen können ... aber richtig, ich denke, das Problem könnte einfacher werden, wenn der (durchschnittliche?) Grad steigt.

Lev Reyzin

Ich werde einige Simulationen planen, um zu sehen, wie es läuft, wenn der Abschluss wächst.

Sylvain Peyronnet

Tatsächlich sieht es so aus, als würde diese LB (mit einigen Modifikationen) auch dann gelten, wenn die beiden Enden des Pfades große Cliquen haben - wie in 2 Cliquen auf n / 4, die durch einen Pfad von n / 2 Knoten verbunden sind. Jetzt ist der durchschnittliche Grad O (n), aber Sie können n ^ 2 immer noch nicht schlagen. Vielleicht müssen wir einen Mindestgrad auferlegen?

Lev Reyzin

Ja, wir brauchen einen Mindestabschluss :(

Sylvain Peyronnet

Ich möchte auf die Beziehung zwischen diesem Problem und dem Sortieren von Netzwerken hinweisen. Wenn Ihr Diagramm beispielsweise ein Pfad ist, zeigt das triviale Sortiernetzwerk mit linearer Tiefe auch, dass Sie jede Permutation in linearer Anzahl von Runden erhalten können. Darüber hinaus ist dies eng, da das einfache Vertauschen der Elemente an den Endpunkten des Pfades eine lineare Anzahl von Runden erfordert.

AKS-Sortiernetzwerke zeigen, dass es Diagramme gibt, in denen Sie eine beliebige Permutation in logarithmischer Anzahl von Runden erhalten können. Für den Fall von Gittergraphen siehe z . B. diese Vorlesungsunterlagen .

(Natürlich sind Sortieren und Mischen unterschiedliche Probleme, aber viele obere und untere Grenzen hängen zusammen. Wählen Sie beispielsweise zufällige Beschriftungen aus und sortieren Sie nach Beschriftungen.)

Jukka Suomela
quelle

Danke für den Zeiger. Ich werde in diese Richtung graben, vielleicht ist es nicht das, was ich hier brauche (ich bin nicht sicher, ob ich die gute Art von Grafik habe), aber es wird sicherlich etwas sein, das ich früher oder später verwenden werde!

Sylvain Peyronnet