Graphs & Algorithms

Instructors

Prof. Dr. Angelika Steger, Konstantinos Panagiotou

Assistants

Torsten Mütze

Time and Place

Thursday, 08.00 - 10.00 a.m., CAB G 61 (Lecture) and 10.00 - 11.00 a.m., CAB G 61 (Exercises)

Exam

Thursday, 29th May, 08.00 - 10.00 a.m., CAB G 61

You may use your lecture notes. This includes: printouts of all information provided during class (slides, exercises and solutions) and all handwritten notes that you may have.

Here you find last year's exam.

Topics

Graphs are an important concept in mathematics and computer science. This lecture presents algorithms for fundamental problems in graph theory. Amongst others, it covers the following topics:

• Trees
• Connectivity
• Matchings
• Hamilton cycles
• Planar graphs
• Coloring
• Extremal graph theory

Participants

Students of Computer Science or Mathematics in the 6th semester or later.

Material

Follow this link (ETH login required)

Exercises

The first exercise session takes place on Feb 28th.

Exercises are not graded, but students are welcome to hand in their solutions until Tuesday evening for the exercises to be discussed on Thursday the same week (drop them at CAB H19.1 in the box "Torsten" or at my office CAB H39.1). The solutions are corrected and commented and handed back during the exercise session on Thursday.

Exercise 1 (Solution)

Exercise 2 (Solution) Note that the sample solution for Problem 2 (computing biconnected components) presented in the exercise session and handed out on the copies contained an error that has now been corrected.

Exercise 3 (Solution)

Exercise 4 (Solution)

Exercise 5 (Solution)

Exercise 6 (Solution)

Exercise 7 (Solution)

Exercise 8 (Solution)

Exercise 9 (Solution) Hint for Problem 2: Find vertices v, x and y with dist(v,x)=dist(v,y)=1, dist(x,y)=2 and deg(v)>=3 and observe that every component of G-x-y contains neighbors of both x and y.

Exercise 10 (Solution)

Exercise 11 (Solution)

Literature

• D. B. West: Introduction to Graph Theory, Prentice Hall, 2001
• R. Diestel: Graph Theory, Springer-Verlag, 2005
• T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
• B. Bollobas: Modern Graph Theory, Springer Verlag, 1998
• The Stony Brook Algorithm Repository: A shortened version of Skiena's Algorithm Design Manual. Covers many important algorithms with downloadable implementations.