Clique-Aufzählungsalgorithmus

9

Ich lese eine alte Arbeit von MC Golumbic über EPT-Graphen (Kantenschnittpunkte von Pfaden in einem Baum). In der Arbeit wird gezeigt, dass die Anzahl der maximalen Cliquen einer EPT-Grapheninstanz polynomisch ist. Es kommt zu dem Schluss, dass, wenn ein Orakel meldet, dass ein Graph ein EPT-Graph ist, es möglich ist, die maximale Clique mit einem Standard-Clique-Aufzählungsalgorithmus zu finden.G

Was sind diese Standard-Clique-Aufzählungsalgorithmen? Wenn es mehr als eine gibt, können wir dann sagen, dass wir einen dieser Aufzählungsalgorithmen verwenden können, wenn die Anzahl der maximalen Cliquen eines Graphen polynomisch ist ? Oder sollten wir einen speziellen Algorithmus von einem generischen Algorithmus ableiten, der einige spezielle Strukturen der Graphklasse verwendet?

Danke im Voraus.

ds.algorithms graph-algorithms clique Arman
quelle

Antworten:

13

Es gibt mehrere ausgabesensitive Algorithmen, um alle maximalen Cliquen in Polynomzeit pro Ausgabe aufzulisten. Einer der frühesten Algorithmen wurde von Tsukiyama, Ide, Ariyoshi und Shirakawa (1977) entwickelt.

  • Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi und Isao Shirakawa: Ein neuer Algorithmus zur Erzeugung aller maximalen unabhängigen Mengen. SIAM J. Comput. 6 (3): 505 & ndash; 517 (1977)

Dies bedeutet, dass, wenn Sie wissen, dass Ihr Graph höchstens polynomiell viele maximale Cliquen aufweist, die Gesamtlaufzeit ihres Algorithmus in der Eingabegröße polynomisch ist.

Yoshio Okamoto
quelle
Leider habe ich keinen Zugang zum Papier. Aber ich bin mir sicher, dass ich danach suche, danke.
Arman
4

Der Algorithmus von Bron-Kerbosch berechnet alle maximalen Cliquen in einem ungerichteten Graphen (siehe Wikipeadia ). Die Laufzeit im ungünstigsten Fall ist O (3 n / 3 ), anscheinend ist sie im Allgemeinen sehr schnell und immer noch der schnellste bekannte Algorithmus zur Berechnung aller maximalen Cliquen. Für eine neuere Referenz siehe die Papiere von V. Stix und Cazals und Karande .

Volker Turau
quelle
2
O(3n/3)3n/33n/3K3,3,...,3
1
Für neuere Arbeiten zu Bron-Kerbosch siehe meine Artikel arxiv.org/abs/1006.5440 mit Strash und Löffler auf der ISAAC 2010 und arxiv.org/abs/1103.0318 mit Strash auf der SEA 2011. Dies beantwortet jedoch nicht wirklich die Frage des Originalplakats Da der Algorithmus nicht ausgabesensitiv ist, kann er exponentiell lange dauern, selbst wenn es nur polynomiell viele maximale Cliquen gibt.
David Eppstein