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

Digraph Structure Theory IIModule description #40987 / Version 2

← Module page Deutsche Fassung
Module / Version#40987 / #2
ValiditySince Summer semester 2020
Available language(s)English, German
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

OfficeTEL 7-3
Contact personHatzel, Meike Charlotte
E-mail addressstephan.kreutzer@tu-berlin.de
WebsiteNot 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.

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

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Digraph Structure Theory IIExercise3435 L 10588 Summer semester[en]2 ISIS
Digraph Structure Theory IILecture3435 L 10586 Summer semester[en]2 ISIS

Workload and credit points

Digraph Structure Theory II (Exercise)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing154 h60 h
90 h

Digraph Structure Theory II (Lecture)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing154 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:

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

GradingGraded
Exam formatOral exam
LanguageEnglish
Duration/Extent30-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