## Course: Network Algorithms (Netwerkalgoritmen, NA)

In many applications, networks and graphs are used as a model. Tyical examples are networks of roads, or electronic networks. In other applications, the graph model may be less obvious, but appears to be very useful, like for scheduling problems. In this course, we look to the translation of problem to network model, and we look to algorithmic problems and their solutions on networks and graphs.

## Lecturer:

There are two exams, and a number of exercises. The end note for the course of a student is
• 0.3 times the note for the first exam. The first exam tests the first half of the lectures, plus
• 0.3 times the note for the second exam. The second exam tests the second half of the lectures.
• 0.4 times the average note for the exercises. A number of exercise sets will be handed out, on average one set per week. Exercises must be handed in within two weeks after they are given out. The note for the exercises is the average note of them; an exercise set that is not made counts as a 0.
Each of these three parts should have a note of at least 4 to have a sufficient end note. So, both exams count for 30 procent, and the exercises for 40 procent.

It is possible to replace one or both of the exams by an assignment. This can be a literature study, or an experimentation/implementation task. In case a student want to do this, the following rules apply:

• This should be agreed in the first week of the course. The student and lecturer agree on the task with which the exam is replaced.
• The student should follow the lecture each time. Absense due to illness or special circumstances should be discussed with the lecturer.

## Schedule

### Part 1: Paths, flows, and matchings

1. February 7, 2005. Monday. Shortest Paths I.
2. February 9, 2005. Wednesday. Shortest Paths II.
3. February 14, 2005. Monday. The Travelling Salesman Problem.
4. February 16, 2005. Wednesday. Network Flow I.
5. February 21, 2005. Monday. Network Flow II. Minimum Cost Flow I.
6. February 23, 2005. Wednesday. Minimum Cost Flow II.
7. February 28, 2005. Monday. Matching I.
8. March 2, 2005. Wednesday. Matching II. Stable marriage problem.
9. March 7, 2005. Monday. First Exam.

1. March 9, 2005. Wednesday. Graph Isomorphism.
2. March 14, 2005. Monday. Graph Isomorphism on trees. Planarity I.
3. March 16, 2005. Wednesday. Planarity II and Graph Drawing.
4. March 21, 2005. Monday. Trees and Treewidth I. Note that there is no class on Wednesday, March 23 (and neither on 2nd Eastern Day).
5. March 30, 2005. Wednesday. Treewidth II.
6. April 4, 2005. Monday. Sets in Graphs.
7. April 6, 2005. Wednesday. Coloring.
8. April 11, 2005. Monday. The Steiner Tree Problem
9. April 13, 2005. Wednesday. The Steiner Tree Problem; Fixed Parameter Complexity.
10. April 20, 2005. Wednesday. Second Exam. (9-11.)

## Exercises

There will be eight sets of exercises. The exercises will be listed here. For each exercise, there is a deadline for handing in the solution, which is usually two weeks after the moment the relevant material has been lectured.

Solutions should be written out in detail, with carefull explanation of the methods and arguments used, and written legibly, in correct Dutch or English.

1. Exercise 24-5 from Introduction to Algorithms, Cormen et al (2nd edition), page 617, 618. This is exercise 25-5 from the first edition from this book. Deadline: wednesday, February 23, 2005.
2. Postscript file exercise set 2. Pdf file exercise set 2. Postscript file exercise set 2 (english). Pdf file exercise set 2 (english). Deadline: wednesday, March 2, 2005.
3. Exercises 26-1 and 26-5 from Introduction to Algorithms. Deadline: wednesday, March 9, 2005.
4. Postscript file exercise set 4. Pdf file exercise set 4. Deadline: wednesday, March 16, 2005.
5. Postscript file exercise set 5. Pdf file exercise set 5. Deadline: wednesday, March 30, 2005.
6. Postscript file exercise set 6. Pdf file exercise set 6. Deadline: wednesday, april 6, 2005.
7. Postscript file exercise set 7. Pdf file exercise set 7. Deadline: wednesday, april 13, 2005.
8. Postscript file exercise set 8. Pdf file exercise set 8. Deadline: wednesday, april 20, 2005.

## Course overview

There will be two lectures of two hours per week (see schedule.)

During the course, 8 sets of excercise sets are handed out to the students.

The exams and excercises should be at least 4 for a sufficient end note. The end note then is the average of the note for the first test, the note for

## Course overview

There will be two lectures of two hours per week (see schedule.)

During the course, 8 sets of excercise sets are handed out to the students.

The exams and excercises should be at least 4 for a sufficient end note. The end note then is the 0.3 times the note for the first test, plus 0.3 times the note for the second test, plus 0.4 times the average of the notes of the exercises, i.e., 0.3*T1+0.3*T2+0.4*E.

In case the end note is not sufficient, you can do in some cases an addtional exam. You can redo an exam, when
• You have a note that is at least 3 and less than 6 for it. OR:
• You followed all or all but one of the lectures, and have a note less than 3.
(Note that you cannot redo exams which you passed.)

You can do one additional exercise set, whose note then replaces the lowest note obtained for one of the eight exercise sets.

## Powerpoint files

1. Shortest paths.
2. Traveling Salesman Problem.
3. Powerpoint file Maximum flow. (Version 2005b.)
4. Powerpoint file Minimum cost flow. (Version 2005.)
5. Powerpoint file Matching. (Version 2005a, revised February 28, 2005.)
6. Powerpoint file Stable Marriage. (New file: March 1, 2005.)
7. Graph Isomorphism Powerpoint file. (Version 2005.) PDF-file of text on graph isomorphism. (In Dutch.)
8. Power point file Planarity.
9. Power point file Graph drawing: force directed methods. (New: March 15, 2005.)
10. Power point file Treewidth. (Version March 29, 2005.)
11. Power point file Vertex cover and related problems (Version April 28, 2005.).
12. Power point file Coloring.
13. Power point file Steiner Trees. (Version April 14, 2005.)
14. Power point file Fixed Parameter Tractability. (Version April 14, 2005.)

## Literature

The following are recommended sources for this course. It is not necessary to purchase these books for the course.
• Alexander Schrijver, Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag, Berlin, 2003. (3 volumes, 90 euro.) ISBN 3-350-44389-4. CDrom version currently available.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms (2nd edition). The MIT Press/ McGraw-Hill Book Company, 2001. ISBN 0-262-03293-7, or ISBN 0-07-013151-1. (Or the first edition of this book.)
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network flows. Theory, Algorithms, and Applications. Prentice-Haal, Englewood Cliffs, New Jersey, 1993. ISBN 0-13-617549-X.

## Language

In case all participants of the course are Dutch-speaking, the course will be given in Dutch; in all other cases, the course will be given in English.