Looking for algorithm Keywords? Try Ask4Keywords

algorithmPolynom-Zeit-begrenzter Algorithmus für Minimum Vertex Cover


Einführung

Dies ist ein Polynomalgorithmus, um die minimale Scheitelpunktdeckung eines verbundenen ungerichteten Graphen zu erhalten. Die zeitliche Komplexität dieses Algorithmus ist O (n2)

Parameter

Variable Bedeutung
G Eingabe verbundener nicht gerichteter Graph
X Satz von Eckpunkten
C Endgültiger Satz von Scheitelpunkten

Bemerkungen

Das erste, was Sie in diesem Algorithmus tun müssen, um alle Scheitelpunkte des Graphen in absteigender Reihenfolge nach Grad zu sortieren.

Danach müssen Sie sie iterieren und jeden zu den endgültigen Vertices setzen, die keinen benachbarten Vertex in dieser Menge haben.

In der letzten Phase iterieren Sie die letzten Scheitelpunkte und entfernen Sie alle Scheitelpunkte, die einen ihrer benachbarten Scheitelpunkte in diesem Satz haben.

Polynom-Zeit-begrenzter Algorithmus für Minimum Vertex Cover Verwandte Beispiele