Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Structure and Algorithmic Applications of Directed GraphsModule description #40111 / Version 1

← Module page Deutsche Fassung
Module / Version#40111 / #1
ValiditySince WS 2014/15
Available language(s)English
Credit points6
Person responsible for the moduleKreutzer, Stephan
GradingGraded
Exam formatOral exam
Language(s) of instructionEnglish

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34352200 FG Logik und Semantik (LaS)

Contact

OfficeEN 25
Contact personPilz, Jana
E-mail addresslas-lehre@lists.tu-berlin
Websitehttps://www.tu.berlin/las

Learning outcomes

Students taking the course will be familiar with the structure theory for directed graphs. They will be able to model real world computational problems as directed graphs, where applicable, and to apply general algorithmic techniques for solving these problems efficiently.

Content

Graphs are a ubiquitous model in mathematics and computer science and many computational and other problems arising in computer science have graph theoretical abstractions.

In the last few decades a very extensive structure theory for graphs has been developed which has proved to be extremely useful in the design of algorithms for NP-hard computational problems.

However, most of this theory applies in particular to undirected graphs and for directed graphs much less is known.

In this course we will cover structural and algorithmic aspects of directed graphs.

In particular, we will cover
- structural decompositions of directed graphs
- algorithmic applications of this structure theory
- combinatorial results such as the Erdos-Posa property and Younger’s conjecture
- routing and flow problems for directed graphs
- disjoint paths problems for directed graphs
- tournaments
- general algorithmic techniques applicable to digraphs

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Digraph Structure TheoryLecture0401 L 171 Irregular[en]2 ISIS
Digraph Structure TheoryExercise0401 L 172 Irregular[en]2 ISIS

Workload and credit points

Digraph Structure Theory (Lecture)

Workload descriptionMultiplierHoursTotal
Präsenzzeit152 h30 h
Vor-/Nachbereitung + Prüfungsvorbereitung154 h60 h
90 h

Digraph Structure Theory (Exercise)

Workload descriptionMultiplierHoursTotal
Präsenzzeit152 h30 h
Vor-/Nachbereitung + Prüfungsvorbereitung154 h60 h
90 h

The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.

Description of teaching and learning methods

- Lecture presenting the core material
- tutorials in which examples and exercises are discussed

There will not be regular homework. Instead we will work on and discuss exercises in the tutorials with only occasional extra homework.

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

The course is entirely self-contained and all concepts needed will be introduced.

However, this is an advanced course in graph theory covering topics very close to current research. Students taking this course therefore should have a significant interest in graph theory or combinatorics and ideally should have some mathematical maturity, i.e. some experience in combinatorial reasoning.

Mandatory requirements for the module examination registration:

This module has no examination requirements.

Completion of the module

GradingGraded
Exam formatOral exam
LanguageEnglish
Duration/Extent30 Minuten

Duration of the module

The following number of semesters is estimated for taking and completing the module: 1 semester(s).

This module can be started in the following semesters: Winter and summer semester.

Maximum number of participants

This module is not limited to a number of students.

Registration procedures

Die Prüfungsanmeldung erfolgt über QISPOS

ISIS

Recommended reading, lecture notes

Lecture notes

unavailable

Electronic lecture notes

unavailable

Recommended literature

No recommended literature given

Assigned programs

This module version is used in the following programs:

Program / program versionSemester(s)Curriculum component
Computer Engineering
Computer Engineering (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SS 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
Computer Science (Informatik) (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Studiengebiete › Grundlagen der Informatik / Foundations of Computing
SS 2026Studiengebiete › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing
Electrical Engineering
Electrical Engineering (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SS 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing

Miscellaneous

Not specified