Heuristiken für das Maximum Clique Problem

SideWinder

Hallo,

bin auf der Suche nach greedy Heuristiken für das http://en.wikipedia.org/wiki/Maximum_clique_problem . Dabei sind meine Kanten allerdings gewichtet.

Ich kann für die Übung drei Algorithmen umsetzen von denen dann die beste Clique gewertet wird (sofern sie in der Zeit berechnet wird, und über einer gewissen thresHold-Größe liegt).

Ich habe derzeit folgende drei Methoden umgesetzt (alle basieren darauf, einen Knoten hinzuzufügen, und alle nicht mehr gültigen zu löschen - solange bis keine gültigen mehr da sind):

- Wähle den Knoten mit dem höchsten Gesamtgewicht, berechne das Gewicht für alle gültigen Knoten nach jeder Iteration neu
- Wähle den Knoten mit dem höchsten Gesamtgewicht, behalte die Gewichte die zu Beginn gegolten haben
- Wähle den Knoten mit den meisten Nachbarn

Funktioniert wunderbar, bei drei Graphen bin ich allerdings noch nicht über thresHold2 (thresHold1 wird verlangt damit die Abgabe positiv ist, thresHold2 zu überbieten ist sozusagen das Tüpfelchen auf dem i).

Ich will also nun Algorithmus 2 noch austauschen. Kennt jemand noch andere Heuristiken, oder andere Möglichkeiten die bestehenden Heuristiken umzusetzen? In der Literatur findet man entweder das exakte Verfahren (welches jeglichen Zeitrahmen sprengt) oder diese beiden Wege.

Ideen?

MfG SideWinder