Course Description
This course covers a selection of topics from graph theory and the theory of graph algorithms. Possible topics include
- planar graphs (Kuratowski's Theorem, Lipton-Tarjan separators)
- treewidth
- network flows ("push/relabel" method of Goldberg and Tarjan)
- matchings in general graphs (Tutte-Berge Theorem; algebraic algorithms)
- equitable coloring (Hajnal-Szemerédi Theorem, algorithm of Kostocka and Kierstead)
- list coloring (Galvin's Theorem, stable matching algorithm)
- extremal graph theory (Erdős-Stone Theorem, Szemerédi's Regularity Lemma)
- property testing
Literature
- D. B. West: Introduction to Graph Theory, Prentice Hall, 2001.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 2nd edition, MIT Press and McGraw-Hill, 2001.
- A. Steger, Skript zur Vorlesung "Graphenalgorithmen", 2005. (in German)
- H. A. Kierstead and A. V. Kostochka, A Short Proof of the Hajnal-Szemerédi Theorem on Equitable Coloring, manuscript, 2006.
- R. Diestel Graph Theory, Springer-Verlag, Heidelberg. (freely available electronic edition in English and German)
- E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97-126. Also in: Current Trends in Theoretical Computer Science: The Challenge of the New Century (G. Paun, G. Rozenberg and A. Salomaa eds.), World Scientific Publishing (2004), Vol. I 229-264.
- J. Matousek, Chapter 5 in Lecture Notes to the Core Subject course "Algorithms, Probability, and Computing", Computer Science Department, ETH Zurich, September 2007.
- N. J. A. Harvey, Algebraic Algorithms for Matching and Matroid Problems, SIAM Journal on Computing, to appear.
Course Material
Content Slides Exercises Notes Basics, Separators in planar graphs Prerequisites, Separators - Kuratowski's Theorem Slides - Kuratowski's Theorem cont'd, Treewidth - - Treewidth Slides - Treewidth, Network Flows - - Network Flows: preflow-push Slides - Relabel-to-front, Equitable colorings - - Equitable colorings (Hajnal-Szemerédi) Slides - Fast equitable coloring; Turán-type problems Slides - Erdős-Stone Theorem, Regularity Lemma - - Regularity Lemma, Property Testing Slides - Matchings, Tutte's Theorem Slides - Maximum Matching Algorithms Slides - -
No comments:
Post a Comment