252-1408-00L  Graphs and Algorithms

SemesterSpring Semester 2014
LecturersJ. Lengler, A. Ferber
Periodicityyearly recurring course
Language of instructionEnglish


AbstractConnectivity (block decomposition, Menger), Matching for bipartite graphs (Hall, König, Hopcroft-Karp algorithm, Hungarian method), Hamilton cycles (Dirac), Planar graphs (Euler’s formula, 5-coloring, planarity testing (in quadratic time)), Graph Coloring (Greedy, Brooks, Erdös' argument, Vizing, Hadwiger’s conjecture), Extremal Graph Theory (Ramsey, Turan)
ObjectiveThe students will get an overview over the most fundamental questions concerning graph theory, and will encounter selected algorithm that demonstrate basic graph computational techniques.

After the lecture, we expect the students to be able to apply the presented algorithmic techniques to the problems discussed in class, and to variations thereof. We expect them to understand the proof techniques and to use them autonomously on related problems.

With the graded homeworks the students will practice to formulate their own proofs and to use LaTeX in order to write them up.

In the algorithmic aspects, the focus of the lecture will be rather on the graph theoretic ideas than on implementation details like the underlying data structures. Likewise, the superior aim of the algorithmic parts of the lecture is to master and transfer the techniques rather than being able to recite all implementation details.
Lecture notesLecture slides will be provided. Parts of the lecture (in particular some of the proofs) will not be on the slides but only at the blackboard.
LiteratureWest, D.: "Introduction to Graph Theory"
Diestel, R.: "Graph Theory"
Bondy, J.A; Murty, U.S.R: "Graph Theory"

Further literature links will be provided in the lecture.