Home » Graphs AND Algorithms: Advanced Topics » GRAPHS AND ALGORITHMS PDF PPT SLIDES

GRAPHS AND ALGORITHMS PDF PPT SLIDES

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 PDF -

Kuratowski's Theorem Slides PDF -

Kuratowski's Theorem cont'd, Treewidth - PDF -

Treewidth Slides PDF -

Treewidth, Network Flows - PDF -

Network Flows: preflow-push Slides PDF -

Relabel-to-front, Equitable colorings - PDF -

Equitable colorings (Hajnal-Szemerédi) Slides PDF -

Fast equitable coloring; Turán-type problems Slides PDF -

Erdős-Stone Theorem, Regularity Lemma - PDF -

Regularity Lemma, Property Testing Slides PDF -

Matchings, Tutte's Theorem Slides PDF -

Maximum Matching Algorithms Slides - -

Thank you for reading the article about GRAPHS AND ALGORITHMS PDF PPT SLIDES. If you want to duplicate this article you are expected to include links https://immunologyebooks.blogspot.com/2011/09/graphs-and-algorithms-pdf-ppt-slides.html. Thank you for your attention.


Content	Slides	Exercises	Notes

Basics, Separators in planar graphs	Prerequisites, Separators	PDF	-

Kuratowski's Theorem	Slides	PDF	-

Kuratowski's Theorem cont'd, Treewidth	-	PDF	-

Treewidth	Slides	PDF	-

Treewidth, Network Flows	-	PDF	-

Network Flows: preflow-push	Slides	PDF	-

Relabel-to-front, Equitable colorings	-	PDF	-

Equitable colorings (Hajnal-Szemerédi)	Slides	PDF	-

Fast equitable coloring; Turán-type problems	Slides	PDF	-

Erdős-Stone Theorem, Regularity Lemma	-	PDF	-

Regularity Lemma, Property Testing	Slides	PDF	-

Matchings, Tutte's Theorem	Slides	PDF	-

Maximum Matching Algorithms	Slides	-	-