Seminar: Dekompositionsmethoden in der diskreten Optimierung (WS 2014)

Thema	Student	Betreuer
Combinatorial Optimization on graphs of bounded treewidth [Bodlaender and Koster (2008)]	tba	tba
Edge dominating set and colorings on graphs with fixed clique-width [Kobler, Rotics (2003)]	tba	tba
Tour merging via branch-decomposition [Cook and Seymour (2003)]	tba	tba
On Integer Programming and the Branch-Width of the constraint matrix [Cunningham and Geelen (2007)]	tba	tba
Dominating sets in planar graphs: Branch-Width and exponential speed-up [Fomin and Thilikos (2003)]	tba	tba
Call Routing and the Ratcatcher [Seymour and Thomas (1994)]	tba	tba
Finding Branch-Decompositions and Rank-Decompositions [Oum and Hlineny (2008)]	tba	tba
Treewidth Computations I: Upper Bounds [Bodlaender and Koster (2010)]	tba	tba
Treewidth Computations II. Lower Bounds [Bodlaender and Koster (2011)]	tba	tba
On exact algorithms for treewidth [Bodlaender et al. (2012)]	tba	tba

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:

Die wesentliche Leistung ist ein Vortrag von ca. 60 Minuten über das zugeteilte Thema. Im Vortrag sollen in verständlicher Form wichtige Ergebnisse des (für den Vortrag zentralen) Artikels vorgestellt werden. Ausgewählte Beweise sollen erklärt werden. Anwesenheit bei allen Vorträgen ist Pflicht! Bei Konflikte (z.B. Prüfungen oder Vorlesungen) muss der Betreuer im Voraus informiert werden.
Die Vortragsform und -medien kann jeder frei wählen. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Bei einem Beamervortrag sind die Folien eine Woche vor dem Vortrag einzureichen.
Eine Woche vor dem Vortragstermin ist von den Vortragenden eine etwa 5-seitige Ausarbeitung zum Thema vorzulegen. Diese wird an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen wesentliche Definitionen und Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in "Publikationsqualität" vorliegen. Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley.)

Bei der Literatursuche sind folgende Links nützlich:

Zuletzt aktualisiert: 17. Februar 2014

Master-Seminar: Dekompositionsmethoden in der diskreten Optimierung