Algorithmic Graph TheoryModule description #40822 / Version 1
- 6 CP
- Oral exam
- Graded
- Summer semester
- English
| Module / Version | #40822 / #1 |
|---|---|
| Validity | Since SS 2017 |
| Available language(s) | English |
| 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 | Not specified |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | Not specified |
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.
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
- 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
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Algorithmische Graphentheorie (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Algorithmische Graphentheorie (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 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
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 examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Type of portfolio examination | 100 points in total |
| 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(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
See http://logic.las.tu-berlin.de
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
No recommended literature given
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science Computer Science (B. Sc.) - StuPO 2015 | SS 2025 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik |
| WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Katalog Informatik | |
| Computer Science Computer Science (B. Sc.) - StuPO 2025 | WS 2026/27 | Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Natural Sciences in the Information Society StuPO 2018 | SS 2025 | Wahlpflichtbereich › Informatik › Weiterführende Module |
| WS 2025/26 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| SS 2026 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| WS 2026/27 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| Natural Sciences in the Information Society Natural Sciences in the Information Society (B. Sc.) - StuPO 2025 | WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
Miscellaneous
Not specified