Moses - Algorithmische Graphentheorie

Display language

To modulepage Generate PDF

Module / Version:
#40822 / #1

Validity:
Seit SS 2017

Default display language:
English

Module title:
Algorithmische Graphentheorie
Algorithmic Graph Theory

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:
No information

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

Website:
No information

Learning Outcomes

Many real world computational problems can be modeled as graph theoretical problems. In this course we will present algorithmic concepts and methods for solving various types of graph theoretical problems, including colouring problems, matchings, various types of cut and connectivity problems. In the basic algorithms and data structures course efficient (polynomial time) algorithms for network flow and other problems have been studied. In this course we will cover additional types of problems that can be solved efficiently such as computing maximal matchings. We will also study NP-hard problems and discuss various attempts of solving these problems efficiently, e.g. by approximating the solution or isolating the exponential running time in a single parameter. Besides the algorithmic techniques, the course will also focus on the pure graph theoretical methods that make efficient algorithmic solutions possible.

Content

In the course we will cover the following topics: - Basic definitions of graphs and digraphs - Basic concepts of algorithms and complexity - Connectivity and Cuts - Matchings - Graph Colourings - Tree-Width - 3-Connectivity and Tutte's Theorem - Planar graphs

Module Components

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Algorithmische Graphentheorie	VL	3435 L 9053	SoSe	No information	2
Algorithmische Graphentheorie	UE	3435 L 9054	SoSe	No information	2

Workload and Credit Points

Algorithmische Graphentheorie (VL):

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

Algorithmische Graphentheorie (UE):

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

The course consists of a lecture delivered in an interactive style using black board proofs and slides.

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

It is desirable that students taking the course have taken an introduction to graph theory. The course is mostly self-contained, though, but assumes some familiarity with graph theoretical medthods.

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

20-40 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:
Sommersemester.

Maximum Number of Participants

This module is not limited to a number of students.

Registration Procedures

See http://logic.las.tu-berlin.de

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	15	SS 2017	SoSe 2024
Computer Science (Informatik) (M. Sc.)	1	25	SS 2017	SoSe 2024
Elektrotechnik (M. Sc.)	1	15	SS 2017	SoSe 2024
Informatik (B. Sc.)	1	16	SS 2017	SoSe 2024
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)	3	3	SoSe 2024	SoSe 2024

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

Miscellaneous

No information

Algorithmische Graphentheorie