Moses - Digraph Structure Theory II

Display language

To modulepage Generate PDF

Module / Version:
#40987 / #2

Validity:
Seit SoSe 2020

Default display language:
English

Module title:
Digraph Structure Theory II

Credits:
6

Responsible person:
Kreutzer, Stephan

Grading:
benotet

Type of exam:
Mündliche Prüfung

Zugehörigkeit

Faculty:
Fakultät IV

Institute:
Institut für Softwaretechnik und Theoretische Informatik

Area of expertise:
34352200 FG Logik und Semantik

Prüfungsausschuss:
No information

Kontakt

Office:
TEL 7-3

Contact person:
Hatzel, Meike Charlotte

E-mail address:
stephan.kreutzer@tu-berlin.de

Website:
No information

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

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Digraph Structure Theory II	UE	3435 L 10588	SoSe	English	2
Digraph Structure Theory II	VL	3435 L 10586	SoSe	English	2

Workload and Credit Points

Digraph Structure Theory II (UE):

Workload description	Multiplier	Hours	Total
Attendance	15.0	2.0h	30.0h
Pre/post processing	15.0	4.0h	60.0h
			90.0h(~3 LP)

Digraph Structure Theory II (VL):

Workload description	Multiplier	Hours	Total
Attendance	15.0	2.0h	30.0h
Pre/post processing	15.0	4.0h	60.0h
			90.0h(~3 LP)

The Workload of the module sums up to 180.0 Hours. Therefore the module contains 6 Credits.

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 test application:

This module has no requirements.

Module completion

Grading

graded

Type of exam

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.

This module may be commenced in the following semesters:
Sommersemester.

Maximum Number of Participants

This module is not limited to a number of students.

Registration Procedures

registration done via qispos

Recommended literature
No recommended literature given

Assigned Degree Programs

This module is not used in any degree program.

Students of other degrees can participate in this module without capacity testing.

Miscellaneous

No information

Digraph Structure Theory II