Instructors
Topics
Graphs are an important concept in mathematics and computer
science. This lecture presents algorithms for fundamental problems in
graph theory. Amongst others, it covers the following topics:
- Trees
- Connectivity
- Matchings
- Hamilton cycles
- Planar graphs
- Coloring
- Extremal graph theory
Material
- Lecture 2: Bridg-it, Cayley's Formula, and DFS (PDF)
- Lecture 3: Connectivity, Menger's Theorem (PDF)
- Lecture 4: Menger's Theorem (Part II) (PDF)
- Lecture 5: Min-Max Relations and Matchings (PDF)
- Lecture 6: Weighted bipartite matchings and TSP (PDF)
- Lecture 7: Planar Graphs: Euler's Formula and Coloring (PDF)
- Lecture 8: Planar Graphs: Coloring and Drawing (PDF)
Exercises
- Assignment 1: Trees
- Assignment 2: Cayley's Formula and block decomposition
- Assignment 3: Menger's Theorem
- Assignment 4: Matchings in bipartite graphs
- Assignment 5: Matchings and Min-Max Duality
- Assignment 6: Hamiltonian cycles and TSP
- Assignment 7: Planar Graphs
- Assignment 8: Planar Graphs II
- Assignment 9: Coloring I
- Assignment 10:Coloring II
- Assignment 11: Edge Coloring
- Assignment 12: Vertex Coloring and Edge Coloring
Literature
- D. B. West: Introduction to Graph Theory, Prentice Hall, 2001
- R. Diestel: Graph Theory, Springer-Verlag, 2005
- T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
- B. Bollobas: Modern Graph Theory, Springer Verlag, 1998
- The Stony Brook Algorithm Repository: A shortened version of Skiena's Algorithm Design Manual. Covers many important algorithms with downloadable implementations.
No comments:
Post a Comment