Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

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

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Lecturers
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

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:

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