DM867: Combinatorial Optimization

Partial list of Litterature

• Christos Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization, Dover. This is the course text and can be bought in the bookstore for 198 d.kr
• Alexander Schrijver, A course in Combinatorial Optimization, notes from CWI, January 2009. Available from the course page for download (with permission from A. Schrijver).
• Samir Khuller, Design and analysis of Algorithms: Course notes. Available from the course page (with permission from S. khuller).
• Jørgen Bang-Jensen og Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Verlag 2001. Available for free download from this page.

Exam problems

• First set of exam problems
• LaTeX file of first set of exam problems
• Second set of exam problems
• LaTeX file of second set of exam problems

• Note 1
• Note 2
• Note 3
• Note 4
• Note 5
• New version of Note 5
• Note 6
• Note 7
• New version of Note 7
• Note 8
• Note 9
• Note 10
• Note 11
• Note 12
• Note 13
• Note 14 (including the exam questions)

Slides

• Slides on Matroids
• Slides on Max-back orderings
• Solutions to exercises on Note 3
• Slides on general matching
• Solutions to some of the exercises on Note 4
• Solutions to exercises on Note 5
• DM817 Lecture on Edmonds-branching theorem
• Slides on the Gomory-Hu algorithm
• DM817 Lecture on flow applications
• DM817 Lecture on minimum cost flows
• Slides on Matroid Intersection
• Slides on Matroid Union
• Slides on Chordal graphs
• Slides on Lexicographic Breath First Search
• Slides on (algorithmic) properties of chordal graphs
• Slides on Tree-width part 1
• Slides on Tree-width part 2
• Slides on Color Coding

Supplementary Notes

• Alon et al. Color-coding paper from STOC 94
• paper on arc-disjoint subdigraphs in digraphs
• paper on Arc-disjoint flows in digraphs
• The minimum spanning strong subdigraph problem is fixed parameter tractable, J. Bang-Jensen and A. Yeo, Disc. Appl. Math. 156 (2008) 2924-2929
• The paper 'A quadratic kernel for feedback vertex set', S. Thomasse, SODA 2009 pages 115-119.
• Chapter 10 on Tree decompositions of Graphs from the book: R. Niedermeier, Invitation to fixed parameter algorithms, Oxford Lecture Seriers 2006.
• Chapter 4 on Triangulated graphs of M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
• Chapter 13 (Matroids) of Korte and Vygen, Combinatorial Optimization, Springer Verlag 2002
• Section 8.6 of Korte and Vygen, Combinatorial Optimization, Springer Verlag 2002
• Sections 14.5-14.6 of Jungnickel, Graphs, Networks and Algorithms, Springer Verlag, 2005
• A proof of Theorem 10.4 in PS
• Link to Bang-Jensen and Gutin, Digraphs
• Schrijver: A course in Combinatorial optimization
Khuller: Design and analysis of algorithms: course notes from 2012
• Notes by Bjarne Toft on algoritmic combinatorics (in danish)
  • Intoduktion
  • Kapitel 1
  • Kapitel 2
  • Kapitel 3
  • Appendiks
• Notes on Maximum adjacency orderings by Mette Eskesen
• Chapter 12 from the book 'Approximation algorithms' by Vazirani, Springer Verlag