English English

General Information

ECTS: 6
RWTHonline: here
Type When / Where First session Lecturer
V3 Tue, 16:30 - 18:00 / AH II
Wed, 08:30 - 10:00 / AH I
09.10.2018
10.10.2018
Unger

Ü2 Tue, 12:30 - 14:00 / 4017
Wed, 12:30 - 14:00 / 4017
30.10.2018
31.10.2018
Goeke
Viehmann


News

  • 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.

Examinations

More information will come.

Topic

Algorithms 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)

Exercises

To 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.

General remarks:

  • 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.

Literature

  • 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