KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 04.12.2014, Lektion 10

Wagner, Dorothea

Abstract:

10: Vorlesung: NP-Vollständigkeit | Das Problem 3-SAT | Beweis: NP-Vollständigkeit von 3-SAT | Das Problem 2SAT | Das Problem MAX2SAT | Das Problem CLIEQUE | Beweis: NP-Vollständigkeit von CLIQUE | Das Problem COLOR | Beweis: NP-Vollständigkeit von 3COLOR | Konstruktion von 3COLOR-Instanz G | Beispielgraph zur Reduktion | Polynomialität der Reduktion


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 21.08.2015
Erstellungsdatum 04.12.2014
Sprache Deutsch
DOI 10.5445/DIVA/2015-567
Identifikator KITopen-ID: 1000113233
Lizenz KITopen-Lizenz
Serie Theoretische Grundlagen der Informatik, WS 2014/15
Folge 13
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page