- 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 existieren.Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen Sj gesucht oder, falls den Teilmengen Sj Bewertungen cj zugeordnet sind, eine Packung mit maximaler Bewertung.
Das Mengenpackungsproblem 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.
Siehe auch
Literatur
- Michael R. Garey and David S. Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979, ISBN 0-7167-1045-5, A3.1 SP3, S. 221.
Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
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 eine Vereinigung von k oder weniger Teilmengen… … 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
Mengenpackungsproblem
18+
© Academic, 2000-2024
- Kontaktieren Sie uns: Unterstützung, Werbung
Wörterbücher Export, schritte mit PHP, Joomla, Drupal, WordPress, MODx.