Knotenüberdeckungsproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Knotenüberdeckungsproblem (oft mit VERTEX COVER notiert) ist ein Problem der Graphentheorie.

Es fragt, ob zu einem gegebenen einfachen Graphen und einer natürlichen Zahl k eine Knotenüberdeckung der Größe von höchstens k existiert. Das heißt, ob es eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, so dass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist.

Das Knotenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.