DM817: Network Programming

Litterature

• Main text: Ahuja, Magnanti and Orlin: Network Flows: Theory, Algorithms and Applications, Prentice Hall 1993. The book is available in the bookstore, see here
• Supplementary text: Bang-Jensen og Gutin, Digraphs: Theory, Algorithms and Applications, Springer Verlag 2001. You can download a free PDF with the whole book here

Link to Orlins homepage

Weekly Notes etc

• Weekly note 1
• Weekly note 2
• Weekly note 3
• Weekly note 4
• Weekly note 5
• Weekly note 6
• Weekly note 7
• Weekly note 8
• Weekly note 9
• Weekly note 10

Slides from Videos where I solve exercises

1. First set of exercises
2. Second set of exercises
3. Third set of exercises
4. Forth set of exercises
5. Part A of 2020 Exam
6. Exercises on Weekly Note 6
7. Exercises on Weekly note 7+8 (part of)
8. Exercises on Weekly note 10

Slides from video lectures

1. Lecture 1: BJG Sections 3.1.-3.2
2. Lecture 2: BJG Sections 3.3-3.4
3. Lecture 3: BJG Section 3.5 Maximum flows
4. Lecture 4: BJG Section3.5 Integrality Theorem
5. Lecture 5: BJG Section 3.8 Circulations
6. Lecture 6: BJG Section 3.9 Minimum value flows
7. Lecture 7: BJG 7.3 Menger's Theorem
8. Lecture 8: BJG 3.11.1 Bipartite matching
9. Lecture 9: BJG 3.6.1 The Edmonds-Karp algorithm
10. Lecture 10: BJG 3.6.2 Dinic's algorithm
11. Lecture 11: Ahuja application 1.3
12. Lecture 12: Preflow push algorithm
13. Lecture 13: FIFO preflow push algorithm
14. Lecture 14A: unit capacity networks
15. Lecture 14B: simple unit capacity networks
16. Lecture 15: optimality conditions for min cost flows
17. Lecture 16: Min cost flows
18. Lecture 17: flow applications
19. Lecture 18: flows in bipartite networks
20. Lecture 19: flows in planar networks
21. Lecture 20: the primal-dual algorithm
22. Lecture 21: sensitivity analysis for min cost flows
23. Lecture 22: Capacity scaling algorithm for min cost flows.
24. Lecture 23: Submodularity and Menger's theorem
25. Lecture 24: Arc-connectivity augmentation
26. Lecture 25: Convex cost flows
27. Lecture 26: Arc-disjoint branchings
28. Lecture 27: Maximum weight closures
29. Lecture 28: min cost branchings
30. Lecture 29: submodular flows

Previous exam projects (the evaluation used to be by written projects)

• Project A Spring 2018
• Project B Spring 2018
• First part of the exam problems 2020
• Second part of the exam problems 2020

Supplementary Notes

• Bang-Jensen and Gutin, Digraphs in PDF
• Paper by Cherkassky and Goldberg on negative cycle detection (finding a negative cycle)
• pages 342-345 in Bang-Jensen and Gutin Digraphs, 2nd edition on minimum cost branchings.
• Notes on how to use Hoffman's circulation theorem