Optimaler Algorithmus zum Ermitteln des Umfangs eines spärlichen Graphen?

Ich frage mich, wie man den Umfang eines spärlichen ungerichteten Graphen findet. Mit spärlich meine ich . Mit optimal meine ich die geringste zeitliche Komplexität.$|E|=O(|V|)$

Ich dachte über eine Modifikation von Tarjans Algorithmus für ungerichtete Graphen nach, fand aber keine guten Ergebnisse. Eigentlich dachte ich, wenn ich in eine 2-zusammenhängende Komponente finden könnte , dann könnte ich den Umfang durch eine Art Induktion finden, die vom ersten Teil an erreicht werden kann. Ich kann jedoch auf dem falschen Weg sein. Jeder Algorithmus, der asymptotisch besser als Θ ( | V | 2 ) ist (dh o ( | V | 2 ) ), ist willkommen.$O(|V|)$$\Theta(|V|^2)$$o(|V|^2)$

Folgendes weiß ich über das Umfangsproblem in ungerichteten, ungewichteten Diagrammen. Erstens, wenn der Umfang gerade ist, können Sie ihn in -Zeit bestimmen - dies ist ein altes Ergebnis von Itai und Rodeh (A. Itai und M. Rodeh. Finden eines minimalen Stromkreises in einer Grafik. SIAM J Computing, 7 (4): 413–423, 1978.). Die Idee dabei ist: Starten Sie für jeden Scheitelpunkt in der Grafik ein BFS, bis der erste Zyklus geschlossen ist (halten Sie dann an und fahren Sie mit dem nächsten Scheitelpunkt fort); Gibt den kürzesten gefundenen Zyklus zurück. Wenn der Umfang gerade ist, ist der kürzeste gefundene Zyklus der kürzeste Zyklus. Insbesondere wenn Ihr Graph zweiteilig ist, wird der Umfang immer berechnet. Wenn der Umfang g jedoch ungerade ist, finden Sie einen Zyklus der Länge g oder g $O(n^2)$$g$$g$ , so können Sie von 1 sein .$g+1$$1$

Das eigentliche Problem bei einem ungewöhnlichen Umfang ist, dass Ihr Algorithmus zwangsläufig erkennen muss, ob der Graph ein Dreieck hat. Die besten Algorithmen verwenden hierfür die Matrixmultiplikation: min { n 2,38 , m 1,41 ) Zeit für Graphen auf n Knoten und m Kanten. Itai und Rodeh haben auch gezeigt, dass jeder Algorithmus, der ein Dreieck in dichten Graphen findet, auch den Umfang berechnen kann. Wir haben also einen O ( n 2,38 ) -Zeitumfangsalgorithmus. Die Laufzeit für den Umfang in dünnen Diagrammen ist jedoch nicht so gut wie für das Auffinden von Dreiecken. Das Beste, was wir im Allgemeinen wissen, ist O ( $O($$n^{2.38}, m^{1.41})$$n$$m$$O(n^{2.38})$ . Insbesondere scheint es am schwierigsten zu sein, einen o ( n 2 ) -Zeitalgorithmus für Graphen mit m = O ( n ) zu finden .$O(mn)$$o(n^2)$$m=O(n)$

Wenn Sie sich für Approximationsalgorithmen interessieren, haben Liam Roditty und ich kürzlich in SODA'12 einen Artikel darüber veröffentlicht: Liam Roditty, V. Vassilevska Williams: Subquadratische Zeitnäherungsalgorithmen für den Umfang. SODA 2012: 833 & ndash; 845. Dort zeigen wir, dass eine Annäherung in subquadratischer Zeit gefunden werden kann und einige andere Ergebnisse in Bezug auf additive Annäherungen und Erweiterungen. Im Allgemeinen enthalten dichte Graphen nach einem Satz von Bondy und Simonovits, etwa an n 1 + 1 / k- Kanten, bereits kurze gerade Zyklen, etwa 2 $2$$n^{1+1/k}$$2k$. Je dichter der Graph ist, desto einfacher ist es, eine gute Annäherung an den Umfang zu finden. Wenn der Graph sehr dünn ist, kann der Umfang im Wesentlichen beliebig groß sein.

Das Finden des Umfangs eines planaren Graphen hat eine interessante Geschichte. In diesem Artikel von Chang und Lu finden Sie einen linearen Zeitalgorithmus und die Geschichte der Verbesserungen.

Es gibt keine allgemeine Technik Umfang zu finden jeder spärlich Graphen. Oft müssen wir uns die damit verbundenen speziellen Zerlegungen oder Einbettungen ansehen, um bessere Grenzen zu erreichen. Wenn ein Graph "nachweislich" dünn ist, ist oft eine schöne Struktur damit verbunden. Beispielsweise sind Diagramme mit begrenzter Baumbreite spärlich und weisen die damit verbundenen Baumzerlegungen auf.

$o(n^2)$