| Property |
Value |
| dbo:abstract
|
- 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, ob es eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, so dass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist. Das Knotenü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. Karps 21 NP-vollständige Probleme 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 (de)
- 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, ob es eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, so dass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist. Das Knotenü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. Karps 21 NP-vollständige Probleme 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 (de)
|
| dbo:wikiPageID
| |
| dbo:wikiPageRevisionID
| |
| dct:subject
| |
| rdfs:comment
|
- 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, ob es eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, so dass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist. Das Knotenü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. (de)
- 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, ob es eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, so dass jede Kante des Graphen mit mindestens einem Knoten aus U verbunden ist. Das Knotenü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. (de)
|
| rdfs:label
|
- Knotenüberdeckungsproblem (de)
- Knotenüberdeckungsproblem (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
