Course MAT-52-11-K-7
Graphs and Algorithms (4V+2U, 9.0 LP)
Course Type
SWS | Type | Course Form | CP (Effort) | Presence-Time / Self-Study | |
---|---|---|---|---|---|
- | K | Lecture with exercise classes (V/U) | 9.0 CP | 186 h | |
4 | V | Lecture | 56 h | ||
2 | U | Exercise class (in small groups) | 28 h | ||
(4V+2U) | 9.0 CP | 84 h | 186 h |
Basedata
Contents
- graphs and digraphs,
- graph algorithms, basic complexity terms (P, NP), construction of graphs,
- paths, cycles, connection,
- Eulerian and Hamiltonian cycles,
- colouring and covering,
- location problems on graphs,
- perfect graphs, efficient algorithms for chordal graphs,
- transitive hulls, irreducible kernels,
- trees, forests, matroids,
- search strategies: depth first search, breadth first search,
- matchings,
- planar graphs.
Literature
- S. O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen,
- R. Diestel: Graph Theory,
- F. Harary: Graph Theory,
- M. R. Garey and D. S. Johnson: Computers and Intractability,
- T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to Algorithms.
Materials
Further literature will be announced in the lecture.
Registration
Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de)
Requirements for attendance (informal)
Modules:
- [MAT-10-1-M-2] Fundamentals of Mathematics (M, 28.0 LP)
- [MAT-14-13-M-3] Linear and Network Programming (M, 9.0 LP)
Requirements for attendance (formal)
None
References to Course [MAT-52-11-K-7]
Module | Name | Context | |
---|---|---|---|
[MAT-52-11-M-7] | Graphs and Algorithms | P: Obligatory | 4V+2U, 9.0 LP |