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	Krumke, Sven Oliver, Prof. Dr. (PROF \| DEPT: MAT) + 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