Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 26. Juni 2019 

Knotenüberdeckung


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Eine Knotenüberdeckung ist in der Graphentheorie eine Teilmenge der Knoten eines Graphen die insgesamt mit allen Kanten inzident sind.

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

siehe auch: Cliquen und stabile Mengen



Bücher zum Thema Knotenüberdeckung

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Knoten%FCberdeckung.html">Knotenüberdeckung </a>