77 lines
2.7 KiB
Markdown
77 lines
2.7 KiB
Markdown
Anwendung
|
|
- Greedy anwenden
|
|
- ModifiedGreedy anwenden
|
|
- Sahni anwenden
|
|
- ListScheduling anwenden
|
|
- LPT anwenden
|
|
- RoundRobin anwenden
|
|
- Parallel-Task-Scheduling anwenden
|
|
- TSP1 anwenden
|
|
- Christofides anwenden
|
|
- Strip Packing: NFDH anwenden
|
|
|
|
Vorlesungsbeweis
|
|
- P ⊆ NP zeigen
|
|
- NDTM-Definition ⊆ Verifizierer-Definition zeigen
|
|
- Verifizierer-Definition ⊆ NDTM-Definition zeigen
|
|
- Transitivität von Polynomialzeitreduktionen zeigen
|
|
- Vererbung der NP-Vollständigkeit zeigen
|
|
- L NP-vollständig: L in P <=> P = NP zeigen
|
|
|
|
NP-Vollständigkeit
|
|
- NP-Vollständigkeit zeigen für k-Clique
|
|
- NP-Vollständigkeit zeigen für 3-SAT
|
|
- NP-Vollständigkeit zeigen für VertexCover
|
|
- NP-Vollständigkeit zeigen für CliqueAndIndependentSet
|
|
- NP-Vollständigkeit zeigen für k-CliqueUniversal
|
|
- NP-Vollständigkeit zeigen für Clique-Nomember
|
|
- NP-Vollständigkeit zeigen für k-COLOR-PRECOLORING
|
|
- NP-Vollständigkeit zeigen für FeedbackVertexSet
|
|
- NP-Vollständigkeit zeigen für Delta-Cover
|
|
- NP-Vollständigkeit zeigen für 3-COLOR mit Minimalgrad 3
|
|
- NP-Vollständigkeit zeigen für HamiltonianPath
|
|
- NP-Vollständigkeit zeigen für Hitchhiker's-HamiltonianCycle
|
|
- NP-Vollständigkeit zeigen für TSP-Entscheidung
|
|
- NP-Vollständigkeit zeigen für k-CLIQUE-DEG-3
|
|
- NP-Vollständigkeit zeigen für Partition
|
|
- NP-Vollständigkeit zeigen für SubsetSumCardinality
|
|
- NP-Vollständigkeit zeigen für (a1=1)-SubsetSum
|
|
- NP-Vollständigkeit zeigen für SubsetSum mit Teilbarkeit
|
|
- NP-Vollständigkeit zeigen für SubsetSum ohne Zweierpotenzen
|
|
- NP-Vollständigkeit zeigen für AtMostTwoPerSize-SubsetSum
|
|
- NP-Schwere zeigen für HALT_TM
|
|
|
|
Approximative Algorithmen
|
|
- Güte zeigen für ListScheduling
|
|
- Güte zeigen für LPT
|
|
- Güte zeigen für RoundRobin
|
|
- Güte zeigen für Parallel-Task-ListScheduling
|
|
- Güte zeigen für ModifiedGreedy
|
|
- Güte zeigen für Sahni
|
|
- Güte wiederlegen für Greedy
|
|
- Güte zeigen für TSP1
|
|
- Güte zeigen für Christofides
|
|
- Güte zeigen für 2ApproxVC
|
|
- Güte zeigen für MAX-3-SAT
|
|
- Güte zeigen für ApproximateSubsetSum
|
|
- Güte zeigen für Strip Packing: NFDH
|
|
|
|
ETH
|
|
- ETH-Schranke zeigen für VertexCover
|
|
- ETH-Schranke zeigen für HittingSet
|
|
- ETH-Schranke zeigen für k-Clique
|
|
- ETH-Schranke zeigen für k-IndependentSet
|
|
- ETH-Schranke zeigen für 3-DM
|
|
- ETH-Schranke zeigen für 3-ExactCover
|
|
- ETH-Schranke zeigen für SubsetSum
|
|
- ETH-Schranke zeigen für k-Color
|
|
- ETH-Schranke zeigen für CoverClique
|
|
- ETH-Schranke zeigen für Delta-Cover
|
|
- ETH-Schranke zeigen für NAE-4-SAT
|
|
- ETH-Schranke zeigen für SetSplitting
|
|
- ETH-Schranke zeigen für DominatingSet
|
|
- ETH-Schranke zeigen für GridTiling
|
|
- ETH-Schranke zeigen für SetCover
|
|
- ETH-Schranke zeigen für Scheduling 2|prec, p in {1,2}|Cmax
|
|
- ETH-Schranke zeigen für ILP-Feasibility
|