main page — CS 566 Efficient Algorithms
Unit 9: Graph Algorithms
This unit covers widely used graph algorithms
- basic graph-search algorithms and their applications
- shortest paths
- minimum spanning trees
- network flows
Learning outcomes
- Know basic terminology from graph theory, including types of graphs.
- Know adjacency matrix and adjacency list representations and their performance characteristica.
- Know graph-traversal based algorithm, including efficient implementations.
- Be able to proof correctness of graph-traversal-based algorithms.
- Know algorithms for maximum flows in networks.
- Be able to model new algorithmic problems as graph problems.
Material
— to be added —
Further reading and sources
Graph traversal and its applications are covered in many algorithms books. My presentation takes inspiration from the following sources:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2009), MIT Press
- Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
- Myers, Kozen: Object-Oriented Design and Data Structures lecture notes