|Type||When / Where||First session||Lecturer|
Tue, 16:30 - 18:00 / AH II
Wed, 08:30 - 10:00 / AH I
Tue, 12:30 - 14:00 / 4017
Wed, 12:30 - 14:00 / 4017
- 17.10.2018: Small change in Exercise 1 on Sheet 1.
- 22.10.2018: Small change in Exercise 3 on Sheet 1.
- 24.10.2018: Changed due date for Sheet 2.
- 21.11.2018: Changed explenation in Exercise 4 on Sheet 5.
- 22.11.2018: Changed Exercise 3 on Sheet 5.
- 30.11.2018: Corrected Exercise 1 on Sheet 6.
- 12.12.2018: Exercise Sheet 9 will be the last exercise sheet.
- 08.01.2019: The last lectures are on the 8th and 9th of January. Walter will repeat the most important parts of the lecture and answer questions.
ExaminationsLink to select a date for your oral examination.
TopicAlgorithms for solving classical graph problems on special classes of graphs like intersection graphs, chordal graphs, perfect graphs, planar graphs and graphs with bounded treewidth will be introduced and analyzed in this lecture.
Course Material (only downloadable from within the RWTH-network)
- Chapter 1 slides with transitions.
- Chapter 1 handout without transitions.
- Chapter 2 slides with transitions.
- Chapter 2 handout without transitions.
- Chapter 3 slides with transitions.
- Chapter 3 handout without transitions.
- Chapter 4 slides with transitions.
- Chapter 4 handout without transitions.
- Chapter 5 slides with transitions.
- Chapter 5 handout without transitions.
- Chapter 6 slides with transitions.
- Chapter 6 handout without transitions.
- Chapter 7 slides with transitions.
- Chapter 7 handout without transitions.
- Chapter 8 slides with transitions.
- Chapter 8 handout without transitions.
ExercisesTo achieve the permission for the exam you must earn 50% of the sum of all points and present one of your solutions at least once. Exercises must be done in a group of three, four or five students.
You can earn bonus points for the permission by presenting a special kind of exercise where you should repeat a proof from the lecture in your exercise group. Please look into the exercise sheets for the presentation exercises.
- Blatt 1 [.pdf]
- Blatt 2 [.pdf]
- Blatt 3 [.pdf]
- Blatt 4 [.pdf]
- Blatt 5 [.pdf]
- Blatt 6 [.pdf]
- Blatt 7 [.pdf]
- Blatt 8 [.pdf]
- Blatt 9 [.pdf]
- Exercises are aimed at getting more practice in explaining and presenting proofs or solutions.
- Working in groups for exam preparation is very adviseable.
- Dates for the examinations can be chosen out of a calendar site soon to be found here.
- Bollobás: Advances in Graph Theory
- Bollobás: Graph Theory - An Introductory Course
- Branädt: Special graph classes
- Clark, Holton: Graphentheorie. Grundlagen und Anwendungen
- Diestel: Graph Theory
- Golumbic: Algorithmic Graph Theory and Perfect Graphs
- Harary: Graphentheorie
- Turau: Algorithmische Graphentheorie
- Volkmann: Fundamente der Graphentheorie
- Volkmann: Graphen und Digraphen. Eine Einführung in die Graphentheorie
- West: Introduction To Graph Theory