Partitionieren von Diagrammen bei gleichzeitiger Minimierung der Kanten zwischen Partitionen

Ich arbeite daran, einen triangulierten Graphen in verbundene Untergraphen zu unterteilen, mit einigen Garantien für die Anzahl der Kanten zwischen den Partitionen. Hier ist ein Beispiel eines triangulierten Graphen, der in 4 "Cluster" unterteilt wurde:

Was ich ursprünglich wollte, war ein Algorithmus, der Partitionen von ungefähr k Dreiecken erstellen konnte (es könnte einen Fehler geben, solange er nicht zu groß war), und ich schaffte es, ein herauszufinden. Algorithmus (wobei p die Gesamtzahl der Partitionen ist), der eine solche Partitionierung finden könnte. Dann wurde mir klar, dass eine große Anzahl von Kanten zwischen Partitionen für die Anwendung, für die ich diesen Algorithmus benötigte, nachteilig war.$O(k^2p^2(v+e))$

Idealerweise möchte ich einen Algorithmus, der jede Partition in einem Bereich von , idealerweise einen konstanten Faktor wie 2. Außerdem möchte ich in der Lage sein, die Anzahl der Zwischenkanten mit einer Obergrenze zu versehen das ist "niedrig".$k$

Ein weiteres Problem besteht darin, dass ich eine Partition mit diesen Eigenschaften habe und das Diagramm durch eine der folgenden Aktionen ändere:

• Hinzufügen einer Reihe von Kanten, die mit vorhandenen Scheitelpunkten verbunden sind
• Hinzufügen eines Scheitelpunkts und einer Reihe von Kanten, die mit dem hinzugefügten Scheitelpunkt verbunden sind
• Entfernen einer Reihe von Kanten
• Entfernen eines Scheitelpunkts und aller Kanten, die mit diesem Scheitelpunkt verbunden sind

Ich möchte in der Lage sein, das Diagramm neu zu partitionieren und trotzdem jede Partition mit der Größe und der Anzahl der Schnittkanten zu minimieren. (Dies ist die Lösung, für die ich ein Kopfgeld aufbringe). Dies bedeutet, dass wir mit diesem Algorithmus jede Partition erstellen können, indem wir mit einem leeren Diagramm beginnen und nacheinander Scheitelpunkte und Kanten hinzufügen und neu partitionieren.$k$

Hier sind einige zusätzliche Einschränkungen für das Problem:

• Der Graph ist planar
• Jedes "Dreieck" ist ein Scheitelpunkt mit ungerichteten Kanten zu Dreiecken, mit denen es eine Kante teilt
• Aus der obigen Aussage ist ersichtlich, dass jeder Scheitelpunkt in diesem Diagramm höchstens einen Grad 3 hat
• Der Graph ist verbunden
• Jeder Untergraph von der Partition ist verbunden
• Jeder Untergraph hat ungefähr k Eckpunkte
• Es gibt höchstens Interpartitionskanten (Kanten, die Scheitelpunkte von verschiedenen Partitionen enthalten). Wenn Sie eine ähnliche Grenze für Kanten zwischen Partitionen wie oder , könnte dies auch funktionieren. Ich bin mir nicht ganz sicher, ob die Obergrenze für Kanten zwischen Partitionen kleiner als kann. Wenn Sie also beweisen können, dass es unmöglich ist, bessere Ergebnisse zu erzielen, ist dies ebenfalls zufriedenstellend. 2$\sqrt n$ O(logn)O(n$2\sqrt n$$O(\log n)$$O(n)$

Ich bin an einem Punkt angelangt, an dem ich feststecke, daher wäre jede Hilfe bei diesem Problem sehr hilfreich. Wenn Sie dieses Problem mit aller Kraft lösen können, sind Sie die Bienenknie. Andernfalls würde ich es sehr schätzen, wenn Sie Papiere, Lehrbücher oder Algorithmen kennen, auf die Sie mich hinweisen könnten.

Lassen Sie mich wissen, wenn ich etwas klären muss!

BEARBEITEN: Hier sind einige zusätzliche Einschränkungen, wenn dies das Problem erleichtert.

• Wir haben es mit eingeschränkten Delaunay-Triangulationen zu tun
• Einschränkungen werden NIEMALS ein einzelner Scheitelpunkt sein
• Der aus der Triangulation erstellte Graph ist wie folgt aufgebaut: Jedes Dreieck wird als Scheitelpunkt dargestellt. Jede Kante im Diagramm entspricht einer nicht eingeschränkten Kante in der Triangulation. Dies bedeutet, dass eine eingeschränkte Kante zwischen zwei Dreiecken in der Diagrammdarstellung der Triangulation nicht angezeigt wird.

Eine andere Sache, die mir klar wurde, ist, dass wir möglicherweise modifizieren müssen, um zu wachsen, wenn wächst, andernfalls kann es keine Sub- -Garantien für die Anzahl der Kanten zwischen Partitionen geben.n O ( n $k$$n$$O(n)$

Rao hat zwei Artikel über den spärlichsten Schnitt in planaren Graphen. Eine Annäherung mit konstantem Faktor in quasi-linearer Zeit scheint möglich . Rekursive Halbierung ist zwar nicht ideal, kann jedoch ein praktikabler Ansatz für Ihr Problem sein.

Satish Rao. Finden nahezu optimaler Trennzeichen in planaren Graphen . Im 28. Symposium über Grundlagen der Informatik (FOCS), Seiten 225-237, 1987.

Satish Rao. Schnellere Algorithmen zum Auffinden kleiner Kantenschnitte in planaren Graphen (erweiterte Zusammenfassung). Im 24. ACM-Symposium zur Theorie des Rechnens (STOC), Seiten 229-240, 1992.

Horst D. Simon und Shang-Hua Teng. Wie gut ist die rekursive Halbierung? Im SIAM Journal on Scientific Computing, Band 18, Ausgabe 5, Seiten 1436–1445, 1997.

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf

$O(k^3)$$k = O(\log n)$

Der folgende Algorithmus könnte helfen.

1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.

$O(K)$$O(K)$$O(N/K)$

Auch eine Änderung des Diagramms durch Hinzufügen von Scheitelpunkten würde die Partition nicht beeinflussen. Jede Partition, in der einer der Nachbarn des neuen Scheitelpunkts liegt, kann die Partition des neuen Scheitelpunkts sein. Möglicherweise ist keine Neupartitionierung erforderlich, bis die Größe eines Clusters zu groß wird.

Bearbeiten:

$k$$m$$\mathscr{R}$$k$$\mathscr{R}$$O(K)$$O(K)$$\mathscr{R}$$k$$O(log n)$ dann können die Kanten zwischen den Partitionen reduziert werden.

Ich habe etwas danach gesucht, mich aber beim sofortigen Posten zurückgehalten, um zu sehen, welche anderen Antworten eintreten würden. Ich poste dies jetzt, um einige andere Ideen / Hinweise, die einen gewissen Wert haben könnten, nicht wegzuwerfen (obwohl der Autor der Frage bereits angegeben hat, dass er jetzt eine akzeptable gefunden hat Antworten).

Bei der Inspektion gibt es viele Einschränkungen für dieses Problem, und es könnte möglicherweise ein ganzes Papier erforderlich sein, um einen Algorithmus zu erstellen und zu beweisen, dass er alle erfüllt (was natürlich im Allgemeinen außerhalb des Bereichs des Stapelaustauschformats liegt). Dennoch gibt es einige grundlegende Ansätze, um diese Art von Problem anzugehen

1. empirisch. Generieren Sie zufällige Diagramme, die den Einschränkungen entsprechen, oder verwenden Sie Diagramme aus einem Datensatz, die den Bedingungen entsprechen, und probieren Sie verschiedene Algorithmen aus, um die Leistung zu überprüfen. man kann feststellen, dass ein Algorithmus empirisch die erforderlichen Bedingungen erfüllt. Wenn man strenger ist, könnte man versuchen, aus der empirischen Beobachtung einen Beweis zu erstellen, wenn diese zu 100% durch große Datensätze erfüllt wird. Auch für empirische Untersuchungen ist es oft hilfreich zu wissen, wie die Datensätze erhalten / generiert werden und welche Art / Herkunft sie haben.

2. Die Frage enthält keine verwandten Literaturzitate. Was sind die nächsten Arten von Algorithmen in der Literatur? Für diese Art von Problem können sich mehrere Arten von Forschungsbereichen überschneiden. Es gibt Forschungen zu planaren Graphen, Graphpartitionen, Graphschnitten, Graphentrennern, Partitionierung dreieckiger Graphen usw.; Es ist nicht offensichtlich, das Hauptthema dieser Frage herauszufinden, soweit sie formuliert ist oder welcher bestimmte Forschungsbereich (Graph-Algorithmus) am unmittelbarsten auf sie einwirken würde.

Angesichts dieser Qualifikationen scheint ein Grundthema der Frage "Partitionieren planarer Graphen" zu sein. Hier sind einige der führenden aktuellen Referenzen zu diesem Thema, die hilfreich sein könnten und zusätzliche Themen / Blickwinkel der aktuellen verwandten Forschung zeigen. Es sind einige Algorithmen implementiert, die möglicherweise auf Anfrage der Autoren erhältlich sind.

Die ^dritte beinhaltet die Aufteilung mit Gewichten, die auf gleiche Gewichte verallgemeinert werden, aber einen zusätzlichen Rahmen für die Prüfung / Untersuchung bieten: Könnten alle Fragenbedingungen durch eine Art Gewichtszuweisungsschema erfüllt werden? (Dies könnte auch mit der Anforderung verbunden sein, eine dynamische Steuerung oder Anpassung der Lösungen vorzunehmen, auf die auch in der Frage Bezug genommen wird.)

• Spektrale Partitionierung funktioniert: Planare Graphen und Finite-Elemente-Netze Spielman / Teng

• Lineare Algorithmen für ein k-Partitionsproblem planarer Graphen ohne Angabe von Grundlagen Wada, Chen

• Partitionieren planarer Graphen mit Kosten und Gewichten Aleksandrov et al