Moses - Structure and Algorithmic Applications of Directed Graphs

Display language

To modulepage Generate PDF

Module / Version:
#40111 / #1

Validity:
Seit WS 2014/15

Default display language:
English

Module title:
Structure and Algorithmic Applications of Directed Graphs

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:
Pilz, Jana

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

Website:
No information

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

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Digraph Structure Theory	VL	0401 L 171	k.A.	English	2
Digraph Structure Theory	UE	0401 L 172	k.A.	English	2

Workload and Credit Points

Digraph Structure Theory (VL):

Workload description	Multiplier	Hours	Total
Präsenzzeit	15.0	2.0h	30.0h
Vor-/Nachbereitung + Prüfungsvorbereitung	15.0	4.0h	60.0h
			90.0h(~3 LP)

Digraph Structure Theory (UE):

Workload description	Multiplier	Hours	Total
Präsenzzeit	15.0	2.0h	30.0h
Vor-/Nachbereitung + Prüfungsvorbereitung	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:

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

This module has no requirements.

Module completion

Grading

graded

Type of exam

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.

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

Maximum Number of Participants

This module is not limited to a number of students.

Registration Procedures

Die Prüfungsanmeldung erfolgt über QISPOS ISIS

Recommended literature
No recommended literature given

Assigned Degree Programs

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

This module is used in the following Degree Programs (new System):

Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
Computer Engineering (M. Sc.)	1	9	SoSe 2020	SoSe 2024
Computer Science (Informatik) (M. Sc.)	1	18	SoSe 2020	SoSe 2024
Elektrotechnik (M. Sc.)	1	9	SoSe 2020	SoSe 2024

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

Miscellaneous

No information

Structure and Algorithmic Applications of Directed Graphs