Structure and Algorithmic Applications of Directed GraphsModule description #40111 / Version 1
- 6 CP
- Oral exam
- Graded
- Winter and summer semester
- English
| Module / Version | #40111 / #1 |
|---|---|
| Validity | Since WS 2014/15 |
| Available language(s) | English |
| Credit points | 6 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | EN 25 |
|---|---|
| Contact person | Pilz, Jana |
| E-mail address | las-lehre@lists.tu-berlin |
| Website | https://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
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:
Workload and credit points
Digraph Structure Theory (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung + Prüfungsvorbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Digraph Structure Theory (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung + Prüfungsvorbereitung | 15 | 4 h | 60 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.
- 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.
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
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English |
| Duration/Extent | 30 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
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 version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Miscellaneous
Not specified