Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Teaching

Graphs, Algorithms, and Complexity

Parinya Chalermsook, Erik Jan van Leeuwen

Time: Wednesday, 8.30 (sharp) to 10.00
First meeting: 22nd of April, 2015
Room: 024 on the ground floor of the MPI building (E1.4)
Prerequisites: The only prerequisite is that you are comfortable with mathematical proofs. You are expected to be able to discover and write mathematical proofs on your own. Homework and exam problems will ask you to prove something.
Tutorial: Fridays, 12.00 - 14.00, Room 021 on the ground floor of the MPI building (E1.4). Directed by Sandy Heydrich Takes place only when announced over the mailing list.
Content: The course has two components. First we will cover the basic of graph theory. The goal of this course is to get students exposed to many aspects of graph theory, instead of going deep into selected topics. Then in the second part, we look at selected algorithms and complexity aspects of graphs.
Credits: 5 credits. There will be 3-4 assignments and a final exam. At least half of the homework score is needed for admission into the final exam. The formula for your grade will be max (50% hw + 50% final, 100% final, 100% re-exam).
Exam: Monday, August 3 (probably oral, therefore no time yet)
Re-examFriday, September 11, from 13.00

News for students:
  • Please register for the re-exam by sending Erik Jan an e-mail at erikjan@mpi-inf.mpg.de by Wednesday, September 9.
  • Please subscribe to our mailing list!
Schedule:
Date Instructor Topic References
Apr 22 Parinya Graphs, subgraphs, connected graphs, and trees.
Apr 29 Erik Jan Matching
May 6 Erik Jan Flow and Matching
May 13 Parinya Connectivity
May 20 Erik Jan Planar graphs
May 27 Parinya Stable sets, cliques, and coloring
June 3 May 29 Parinya Stable sets, cliques, and coloring
June 10 canceled
June 17 Erik Jan Treewidth and graph minors
June 24 Parinya Probablistic method and random graphs.
July 1 July 3 Parinya Probablistic method and random graphs (cont.)
July 8 Parinya Expanders and super concentrators
July 15 Erik Jan An Algorithmic View over the Landscape of Graph Classes (part I)
July 22 Erik Jan An Algorithmic View over the Landscape of Graph Classes (part II)
July 29 canceled


Note that classes marked with star (*) may be subject to date changes.

References:

More Courses of the Algorithms and Complexity Group