KomplexitÀt #17 - HAMILTON-Pfad ist NP-hart
0:00 Einleitung 2:16 Reduktion 13:42 Korrektheit 20:23 NP-HĂ€rte fĂŒr Varianten Wir sehen eine Reduktion von 3SAT auf HAMILTON-Pfad an, wodurch wir zeigen, da...
NLogSpace
9.3K views âą Jun 30, 2018
About this video
0:00 Einleitung
2:16 Reduktion
13:42 Korrektheit
20:23 NP-HĂ€rte fĂŒr Varianten
Wir sehen eine Reduktion von 3SAT auf HAMILTON-Pfad an, wodurch wir zeigen, dass HAMILTON-Pfad NP-hart ist. Wir ĂŒberlegen auĂerdem noch, dass die Reduktion auch fĂŒr HAMILTON-Kreis und fĂŒr gerichtete statt ungerichtete Graphen angepasst werden kann.
2:16 Reduktion
13:42 Korrektheit
20:23 NP-HĂ€rte fĂŒr Varianten
Wir sehen eine Reduktion von 3SAT auf HAMILTON-Pfad an, wodurch wir zeigen, dass HAMILTON-Pfad NP-hart ist. Wir ĂŒberlegen auĂerdem noch, dass die Reduktion auch fĂŒr HAMILTON-Kreis und fĂŒr gerichtete statt ungerichtete Graphen angepasst werden kann.
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
9.3K
Likes
183
Duration
22:54
Published
Jun 30, 2018
User Reviews
4.6
(1) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now