Knotenüberdeckungsproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Die Artikel Knotenüberdeckungsproblem und Knotenüberdeckung überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Raynswor (Diskussion) 15:33, 22. Mai 2017 (CEST)

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.