Algorithmen und Komplexität

Seminar: Kombinatorische Optimierung

Dozent: Dr. Stefan Hougardy

---

Termine

Beginn des Seminars: 16.10.2002

SE	Mittwoch	09:00 - 11:00	(RUD 25, 4.110)

Zuordnung

• Hauptstudium, Seminar

Voraussetzungen

• Grundstudium
• Kenntnisse in der Graphentheorie

Inhalte und Lernziele

Viele in der Praxis auftretende Probleme sind kombinatorische Optimierungsprobleme. Ein klassisches Beispiel ist das Traveling Salesman Problem, bei dem es darum geht zu einer gegebenen Menge von Städten eine kürzeste Rundreise durch alle diese Städte zu finden. In diesem Seminar werden für eine Reihe wichtiger Optimierungsprobleme effiziente Algorithmen vorgestellt.

Vortragsthemen

geplante Themen:

• Planaritätstest in linearer Zeit
• Ein linearer Algorithmus für das Steinerbaumproblem
• Effizientes 4-Färben planarer Graphen
• Matchings in allgemeinen Graphen
• polynomieller Test auf Primheit

Empfohlene Literatur

• Hougardy, Prömel, Graphen und Algorithmen 1
• Hougardy, Prömel, Graphen und Algorithmen 2
• Emden-Weinert, Hougardy, Kreuter, Prömel, Steger, Einführung in Graphen und Algorithmen
• Parberry, How to Present a Paper in Theoretical Computer Science: A Speakers Guide to Students

---

zuletzt geändert am 31.07.2006 (alkox-www)