Algorithmen und Komplexität

Vorlesung: Graphen und Algorithmen 2

Dozent: Dr. Stefan Hougardy

---

Termine

Beginn der Vorlesung: 18.04.2001

VL	Montag	11:00 - 13:00	(RUD 25, 3.101)
	Mittwoch	11:00 - 13:00	(RUD 25, 3.101)
UE	Mittwoch	13:00 - 15:00	(RUD 25, 3.101)
PR	n.V.

Zuordnung

• Hauptstudium, 2. Teil eines Kurses
• Theoretische Informatik

Voraussetzungen

• Grundstudium
• Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.

Inhalte und Lernziele

Der Kurs setzt die Vorlesung Graphen und Algorithmen 1 aus dem Wintersemester 2000/2001 fort.

Ein Steinerbaum	Ein zufälliger Graph	Ein extremaler dreiecksfreier Graph

Es werden die folgenden vier Themengebiete vertiefend behandelt:

• Steinerbäume
• zufällige Graphen
• Approximationsalgorithmen und Nichtapproximierbarkeit
• extremale Graphentheorie

Empfohlene Literatur

• Hougardy, Prömel, Graphen und Algorithmen 1
• Hougardy, Prömel, Graphen und Algorithmen 2
• Hougardy, Proof Checking and Non-Approximability
• Hougardy, Prömel, Steger, Probabilistically checkable proofs and their consequences for approximation algorithms
• Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen
• Diestel, Graphentheorie, Springer Verlag, 2000
• West, Introduction to Graph Theory, Prentice Hall, 1996

Links

• Uwes GML-Parser und EPS-Generierer

---

zuletzt geändert am 23.01.2006 (alkox-www)