Duke University

Overview

Graph algorithms are one of the foundational pillars in the study of algorithms, in addition to being applied in a variety of situations in practice. In this course, we will explore some basic developments in graph algorithms over the last seven decades spanning the areas of graph connectivity, distances in graphs, and graph matchings. For each topic, we will try to understand the basic principles underlying classical algorithms for these problems, their inter-connections, and their influences on other areas of algorithm design and combinatorial optimization.

Lectures

Tuesdays and Thursdays at 1:25 - 2:40 pm in LSRC A155

All lectures are in person and will not be recorded. Scribe notes will be posted for every lecture.

References

There is no textbook for the course. Several books will serve as useful references depending on the topic being taught. Some of these books are listed below.

Undergraduate textbooks

[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press.

[DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw Hill.

[KT] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley.

Randomized algorithms

[MR] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press.

[MU] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press.

Approximation algorithms

[V] V. V. Vazirani. Approximation Algorithms. Springer-Verlag.

[WS] D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms. Cambridge University Press.

Online Algorithms

[BE] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press.

Network Flows

[AMO] R. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Combinatorial Optimization

[S] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency (Vol A, B, C).  Springer.