Digraph Structure Theory IIModule description #40987 / Version 2
- 6 CP
- Oral exam
- Graded
- Summer semester
- English
| Module / Version | #40987 / #2 |
|---|---|
| Validity | Since Summer semester 2020 |
| Available language(s) | English, German |
| 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 | TEL 7-3 |
|---|---|
| Contact person | Hatzel, Meike Charlotte |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | Not specified |
Learning outcomes
Students completing this course will gain a deep knowledge of the theory of digraph minors and digraph structure theory based on the concept of strong separations and directed tree-width. They gain a deep understanding of the structural properties of directed graphs.
Students will be able to understand complex proofs in digraph theory and will know the methods and background results to proof results of their own.
Students will be able to understand complex proofs in digraph theory and will know the methods and background results to proof results of their own.
Content
This module is a continuation of "Structure and Algorithmic Applications of Directed Graphs (Digraph Structure Theory I)".
Based on the concepts of directed tree-decompositions and their various forms of obstructions, we will discuss more advanced results in digraph minors and digraph structure theory.
More precisely, we will discuss in detail:
- the directed grid theorem
- the directed flat wall theorem and a directed analogue of the "Local Structure Theorem"
- further structural results for directed graphs, as time permits
Based on the concepts of directed tree-decompositions and their various forms of obstructions, we will discuss more advanced results in digraph minors and digraph structure theory.
More precisely, we will discuss in detail:
- the directed grid theorem
- the directed flat wall theorem and a directed analogue of the "Local Structure Theorem"
- further structural results for directed graphs, as time permits
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Digraph Structure Theory II (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 90 h | |||
Digraph Structure Theory II (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 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:
Students are advised to be familiar with the topics of DST I before starting this course. Beyond that, they should have a strong interest and experience in graph theory.
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-40 minutes |
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: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
registration done via qispos
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
No recommended literature given
Assigned programs
This module is not used in any program.
Miscellaneous
Not specified