Structural Decompositions and Algorithms (186.856)

Course Topic

Decomposition based approaches to tackle computationally hard problems are an integral part in almost all areas of computer science and come with a wide variety of algorithmic applications. The main idea behind decomposition based techniques is to decompose a problem instance into small tractable parts, and to reassemble the solution of the parts to a solution of the entire instance. The course will provide an in-depth coverage of all aspects of the possibly two most important graph decompositions, namely tree-decompositions and clique-decompositions, with a focus on the techniques required for the design of efficient decomposition based algorithms.

Prerequisites

This course assumes prior knowledge from the following courses:
Algorithmen und Datenstrukturen 1
Algorithmen und Datenstrukturen 2
Algorithmics

Lecturers

Prof. Stefan Szeider and Dr. Sebastian Ordyniak