Wir arbeiten daran, die Unionpedia-App im Google Play Store wiederherzustellen
AusgehendeEingehende
🌟Wir haben unser Design fĂŒr eine bessere Navigation vereinfacht!
Instagram Facebook X LinkedIn
Ihre eigene Unionpedia mit Ihrem Logo und Ihrer Domain, ab 9,99 USD/Monat
Mein Unionpedia erstellen

Hitting-Set-Problem

Index Hitting-Set-Problem

Das Hitting-Set-Problem ist ein NP-vollständiges Problem aus der Mengentheorie.

Inhaltsverzeichnis

  1. 4 Beziehungen: Karps 21 NP-vollständige Probleme, Knotenüberdeckung, NP-Vollständigkeit, Richard M. Karp.

Karps 21 NP-vollständige Probleme

Karps 21 NP-vollständige Probleme ist eine in der Komplexitätstheorie gebräuchliche Menge NP-vollständiger Rechenprobleme.

Sehen Hitting-Set-Problem und Karps 21 NP-vollständige Probleme

Knotenüberdeckung

Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält.

Sehen Hitting-Set-Problem und Knotenüberdeckung

NP-Vollständigkeit

NP-schweren und NP-vollständigen Probleme. In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.

Sehen Hitting-Set-Problem und NP-Vollständigkeit

Richard M. Karp

Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston) ist ein amerikanischer Informatiker.

Sehen Hitting-Set-Problem und Richard M. Karp

Auch bekannt als Hitting set.