Knotenüberdeckung

Eine Knotenüberdeckung ist in der Graphentheorie eine Teilmenge der Knoten eines Graphenen, die insgesamt mit allen Kantenn inzident sind.

Das Komplement einer kleinsten Knotenüberdeckung ist in jedem Graph eine größte stabilen Menge. Die Bestimmung beider Größen ist im allgemeinen NP-schwer. In bipartiten Graphen können sie über die Paarungszahl in polynomieller Zeit bestimmt werden.

siehe auch: Cliquen und stabile Mengen