Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen
Zeige Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon

Digitale Medien-Ansicht

Modulnummer
Modulbezeichnung
Sparsity - Graphs and algorithms
Titel (englisch)
Sparsity - Graphs and algorithms
Pflicht/Wahl
Pflicht
Erklärung
CP
6
Berechnung des Workloads
Turnus
I.d.R. angeboten in jedem zweiten Wintersemester
Dauer
ein Semester
Form
2 SWS L, 2 SWS T
Prüfung
i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Anforderungen
Keine
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
Englisch
Bemerkung
Zuletzt geändert
2019-08-20 14:30:01 UTC
Zurück

Zeige Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon