Zum Inhalt springen
Technische Universität Berlin English
Vorlesungsverzeichnis und Modultransfersystem

Algorithmic Graph Structure TheoryModulbeschreibung #40321 / Version 3

← Zur Modulseite English version
Modul / Version#40321 / #3
GültigkeitSeit SoSe 2020
Verfügbare Sprache(n)Englisch
Leistungspunkte9
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Englisch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34352200 FG Logik und Semantik (LaS)

Kontakt

SekretariatEN 25
Ansprechpartner*inPilz, Jana
E-Mail-Adressestephan.kreutzer@tu-berlin.de
Webseitehttps://www.tu.berlin/en/las/studying-and-teaching/course-offer

Lernergebnisse

Students completing the course will understand how structural information about instances to
computational problems can be used in the design of efficient algorithms. They will be familiar
with basic notions of graph decompositions and the algorithmic techniques facilitated to use
this additional information.

Lehrinhalte

Many algorithmic problems on graphs are NP-hard and therefore there is good evidence that no efficient algorithms solving these problems on all graphs exist. Classical examples are
routing problems arising e.g. in integrated circuit layout and design, colouring problems in
scheduling applications or domination problems in facility location.
However, instances to these problems arising in practical applications may have more
”structure“ than general graphs, e.g. instances may be “hierarchical” or “tree-like”. Using this
additional structural information may help in designing efficient algorithms for solving
problems in instances of this form.
A particularly good example are instances which are planar graphs, i.e. graphs that can be
drawn without crossing edges. Planar graphs arise for instance in routing applications, as
many road or train maps are nearly planar. It turns out that if the input instance is planar, or a
tree, then many hard problems become tractable.
In this course we will study methods for solving algorithmic problems on restricted classes of
graphs. The most important cases will be planar graphs and graph classes defined by the
concept of bounded tree-width. We will then extend this to even more general classes of
graphs.
The focus of this lecture is to introduce the structural properties of graphs that can be
employed in the design of efficient algorithms and to present the algorithmic techniques
needed for this.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Algorithmic Graph Structure TheoryIntegrierte Veranstaltung0432 L 674 Unregelmässig[en]4 ISIS
Algorithmic Graph Structure TheoryÜbung Unregelmässig[en]2 ISIS

Arbeitsaufwand und Leistungspunkte

Algorithmic Graph Structure Theory (Integrierte Veranstaltung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit154 h60 h
Vor-/Nachbereitung158 h120 h
180 h

Algorithmic Graph Structure Theory (Übung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung154 h60 h
90 h

Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

The course consists of a flexible mix of lectures and exercise classes. In addition to regular
homework students will be given one more substantial exercise as a mini project over the
course.

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

Participants should have a strong interest in theoretical computer science, discrete
mathematics or algorithmic graph theory.
The course is self-contained in the sense that all relevant algorithmic and graph theoretical
concepts will be introduced in the lectures. Basic knowledge of graph theory and graph
algorithms may be useful but is not a requirement.

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

BenotungBenotet
PrüfungsformMündliche Prüfung
SpracheEnglisch
Dauer/Umfang30 Minuten

Prüfungsbeschreibung (Abschluss des Moduls)

Oral examination
For admission to the oral examination students need to pass the homework set during the
course.

Dauer des Moduls

Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.

Dieses Modul kann in folgenden Semestern begonnen werden: Winter- und Sommersemester.

Maximale teilnehmende Personen

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Registration for the module is via the ISIS System.

To sign up for the exam follow the standard procedures in your curriculum.
Registration via Qispos #60867

Literaturhinweise, Skripte

Skript in Papierform

verfügbar

Skript in elektronischer Form

verfügbar

Empfohlene Literatur

  • Graph Theory by Reinhard Diestel
  • Lecture notes on paper: nein Lectures notes in electronic form: ja Literature: References to additional literature will be given during the lectures.

Zugeordnete Studiengänge

Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOSemesterStudiengangsbereich
Computer Engineering
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Studiengebiete › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Studiengebiete › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing
Elektrotechnik
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Informatik
StuPO 2015
SoSe 2025Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2025/26Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
SoSe 2026Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2026/27Wahlpflichtbereich › Katalog Informatik
Informatik
StuPO 2025
WiSe 2026/27Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module
Wahlpflichtmodul in the Master in Computer Science (Foundations of Computer Science) and Master in Mathematics.
Wahlpflichtmodul Bachelor Computer Science.
Wahlpflichtmodul Bachelor Mathematics.

Sonstiges

The lecture is given in English.