Modulnummer

Modulbezeichnung

Titel (englisch)

Pflicht/Wahl

Erklärung

CP

Berechnung des Workloads

Turnus

Dauer

Form

Prüfung

Anforderungen

Lernziele

• Die Studierenden erlangen Kenntnisse über grundlegende und fortgeschrittene Konzepte aus der Graphentheorie und Algorithmik.
• Die Studierenden erlangen Kompetenzen in der selbstständigen Arbeitsorganisation und sind in der Lage sich komplexe Sachverhalte selbstständig anzueignen.
• Die Studierenden sind in der Lage, komplexe Aufgaben im Team zu lösen.
• Die Studierenden können erarbeitete Ergebnisse präzise und prägnant präasentieren.
• Die Studierenden sind in der Lage, englische Fachtexte zu verstehen und ihre Ergebnisse auf Englisch zu kommunizieren.

Lerninhalte

The theory of bounded expansion and nowhere dense graph classes is a young but rapidly maturing subject. Nowhere denseness provides a very robust notion of uniform sparseness in graphs and many familiar families of sparse graph classes are nowhere dense. These include for example graphs of bounded tree-width, planar graphs, graphs of bounded genus and graphs that exclude a minor or topological minor.

The development of the theory of bounded expansion and nowhere dense graph classes is strongly driven by algorithmic questions. This line of research is based on the observation that many problems, such as the dominating set problem, which are considered intractable in general, can be solved efficiently on restricted graph classes, e.g. on the above mentioned classes of graphs of bounded tree-width, planar graphs, and graph classes excluding a fixed (topological) minor. Many algorithmic results that were first established for specific graph classes can be generalized to nowhere dense classes, and most interestingly, it turns out that nowhere dense classes form a natural limit for many algorithmic techniques for sparse graph classes. In this course we are going to present the structural and algorithmic theory of bounded expansion and nowhere dense graph classes.

The course will be taught in a flipped classroom approach. In a traditional classroom, instructional content is delivered in class through the use of direct instruction. After the class, homework is assigned for students to complete outside the classroom. In contrast, in a flipped classroom, instructional content is prepared and assigned as homework for students to study before coming to class. In-class time is then spent on active learning exercises, such as problem solving, peer collaboration, and discussion. The flipped classroom approach promotes active learning and in this course allows the students to achieve a deep understanding of advanced graph theory and of advanced algorithmic techniques in graph theory.

Contents:

• Basic graph theory
• Treewidth and treedepth
• Graph minor theory
• Bounded expansion and nowhere denseness
• Exact and parameterized graph algorithms
• Approximation algorithms

Quellen

• Vorlesungsskript
• Jaroslav Nesetril and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms. Springer, 2012.
• Marek Cygan et al. Parameterized algorithms. Springer, 2015.

Sprache

Bemerkung

Zuletzt geändert