Mengenüberdeckungsproblem

Mengenüberdeckungsproblem

Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik.

Es fragt, ob zu einer Menge U und n Teilmengen Sj von U und einer natürlichen Zahl k \le n eine Vereinigung von k oder weniger Teilmengen Sj existiert, die der Menge U entspricht (Überdeckung).

Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen Sj gesucht oder, falls den Teilmengen Sj Kosten cj zugeordnet sind, eine Überdeckung mit geringsten Kosten.

Das Mengenü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.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mengenpackungsproblem — Das Mengenpackungsproblem (oft mit set packing Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer endlichen Menge U und n Teilmengen Sj von U eine Anzahl von mindestens paarweise disjunkter Teilmengen Sj… …   Deutsch Wikipedia

  • Cliquenproblem — Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Das Cliquenproblem ist eines der 21 klassischen NP vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies.… …   Deutsch Wikipedia

  • Erfüllbarkeitsproblem der Aussagenlogik — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… …   Deutsch Wikipedia

  • Feedback Vertex Set — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

  • Hamiltonkreisproblem — Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren… …   Deutsch Wikipedia

  • Hitting-Set-Problem — Das Hitting Set Problem ist ein NP vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine… …   Deutsch Wikipedia

  • Karps 21 NP-vollständige Probleme — Eines der bedeutendsten Resultate der Komplexitätstheorie ist der von Stephen Cook im Jahr 1971 erbrachte Nachweis, dass das Erfüllbarkeitsproblem der Aussagenlogik (meist nur kurz SAT genannt) NP vollständig ist. 1972 griff Richard Karp diese… …   Deutsch Wikipedia

  • Knotenüberdeckungsproblem — 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 …   Deutsch Wikipedia

  • Mengenzerlegungsproblem — Das Mengenzerlegungsproblem (oft mit set partitioning Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer Menge U und n Teilmengen Sj von U und einer natürlichen Zahl eine Vereinigung von k disjunkten Teilmengen… …   Deutsch Wikipedia

  • Partitionsproblem — Das Partitionsproblem (auch Zahlenaufteilungsproblem, oft mit PARTITION notiert) ist ein Optimierungs bzw. Entscheidungsproblem der Kombinatorik. Inhaltsverzeichnis 1 Formulierung des Partitionsproblems 2 Phasenübergang im Partitionsproblem …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”