Nächste Seite:
Motivation
Aufwärts:
Graphen und Netzwerke Vorlesung,
Vorherige Seite:
Verbesserungen
Komplexität
Unterabschnitte
Motivation
Turingmaschinen
Beschränkte Maschinen
Komplexitätsklassen
die Klassen P und NP
Reduktion, Vollständigkeit
Beispiele für NPC
Vertex Cover etc.
3-Färbbarkeit
Chordale Graphen
Separatoren
Simpliziale Knoten
Perfect elimination schemes
Perfektion
partielle
k
-Bäume
Algorithmen für
k
-Bäume
Baumweite
Reihen-/Parallel-Graphen
Independent Set für
G
mit beschr. Baumweite
Algorithischer Nutzen der Baumweite
Johannes Waldmann 2005-01-25