Graph Decompositions

Modulnummer: Q06-24
Englischer Titel: Graph Decompositions
Leistungspunkte: 6
Lehrperson: Bergerem

Empfohlene Vorkenntnisse

Solide Grundkenntnisse in den Bereichen Datenstrukturen, Komplexitätstheorie
und Logik

Zwingende Voraussetzungen

keine

Inhalt

Many computationally hard problems become tractable if the underlying structure
of a problem instance is simple. For example, most graph problems are easily
solvable if the graph is a tree. Hence, graph decompositions that decompose
graphs into simpler structures are a useful tool for the design of efficient
algorithms. This course gives an introduction to decompositions of graphs and
other structures. In particular, we consider tree decompositions, which will be
the central notion for most of the course. In addition to characterisations of
such decompositions via combinatorial games, we also study algorithmic
consequences, including powerful algorithmic meta-theorems.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben
- aktive Teilnahme

Lehrveranstaltungen

Vorlesung: 3 SWS 3 LP
Übung: 1 SWS 2 LP
Praktikum: 0 SWS 0 LP
Seminar: 0 SWS 0 LP
Praxisseminar: 0 SWS 0 LP
Projektseminar: 0 SWS 0 LP
MAP: 1 LP

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: nein

Turnus

Unregelmäßig