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 Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon

Informatik-Ansicht

Sparsity - Graphs and algorithms


Sparsity - Graphs and algorithms
Modulnummer
03-ME-602.21
Master
Pflicht/Wahl
Wahl Basis Ergänzung
Sonderfall
Zugeordnet zu Masterprofil
Basis Ergänzung
Sicherheit und Qualität
KI, Kognition, Robotik
Digitale Medien und Interaktion
Modulbereich : Mathematik und Theoretische Informatik
Modulteilbereich : 602 Algorithmen- und Komplexitätstheorie
Anzahl der SWS
V UE K S Prak. Proj.
2 2 0 0 0 0 4
Kreditpunkte : 6 Turnus

I.d.R. angeboten in jedem zweiten Wintersemester

Formale Voraussetzungen : Keine
Inhaltliche Voraussetzungen : Theoretische Informatik 1+2
Vorgesehenes Semester : ab 1. Semester
Sprache : Englisch
Ziele :
  • 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.
Inhalte :

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
Unterlagen (Skripte, Literatur, Programme usw.) :
  • Vorlesungsskript
  • Jaroslav Nesetril and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms. Springer, 2012.
  • Marek Cygan et al. Parameterized algorithms. Springer, 2015.
Form der Prüfung : i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Arbeitsaufwand
Präsenz 56
Übungen + Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. Sebastian Siebertz Verantwortlich Prof. Dr. Sebastian Siebertz
Zurück

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