Knotenüberdeckungsproblem
aus Wikipedia, der freien Enzyklopädie
Das Knotenüberdeckunsproblem (oft mit VERTEX COVER notiert) ist ein Problem der Graphentheorie.
Es fragt, ob zu einem gegebenen einfacher Graph und eine Zahl k eine Knotenüberdeckung der Größe mindestens k existiert. Das heißt, ob der Graph höchstens k Knoten enthält, sodass alle Kanten mit mindestens einem dieser Knoten verbunden sind.
Es gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.
Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen
