# Algorithmic Graph Theory (SS 2012)

26 September 2012 |
A graph describes a binary relation on a set of some elements. In this lecture algorithmic approaches to graph problems such as maximum matching, flows of minimum cost, minimum cycle basis, or vertex coloring are discussed. |

## General Information

Lecture (S. Cornelsen) | Wed 13:30-15:00 (M801) |

Tutorial (M. Baur) | Thu 15:15-16:45 (P601) - fortnightly |

Exams | 1st date: 19 July 2012 (E216) 2nd date: 26 September 2012 (E216): Please sign into a list available at E 214 |

## Assignments

The*assignments*are made available on this webpage as a PDF-file on

**Wednesday at 15:00**. The editing time for each homework is two weeks. The solutions are due in written form until

**Tuesday at 18:00**two weeks later. You can choose to either deposit them in the box marked "Algorithmic Graph Theory" next to room E202, or to submit them electronically in

**one**PDF file to the tutor. In the latter case, please follow the naming schema uXX_name1_name2.pdf, where XX indicates the number of the assignment. We will return the corrected and scored assignments in the tutorial. Whatever is not picked up will be placed back into the box.

The assignments are returned and discussed during the tutorials. 50 percent of the total score of the assignments, regular attendance at the tutorials, and the presentation of at least two of your solutions are necessary to be admitted to the final exam.

*You are permitted and encouraged to work in groups of two.*

No. | Posted | Due Date | Tutorial | Download |
---|---|---|---|---|

1 | 18.04.2012 | 02.05.2012 | 03.05.2012 | |

2 | 09.05.2012 | 22.05.2012 | 24.05.2012 | |

3 | 23.05.2012 | 29.05.2012 | 31.05.2012 | |

4 | 30.05.2012 | 12.06.2012 | 14.06.2012 | |

5 | 13.06.2012 | 26.06.2012 | 28.06.2012 | |

6 | 27.06.2012 | 10.07.2012 | 12.07.2012 |

## Supplementary Material

## Textbooks

- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin: "Network Flows: Theory, Algorithms, and Applications". Prentice Hall, 1993