Graph Algorithms

Department: 
MATH
Course Number: 
7510
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Not regularly scheduled

Algorithms for graph problems such as maximum flow, matching, network reliability, minimum cuts, covering, coloring, planarity, shortest paths, and connectivity. Crosslisted with CS 7510 and ISYE 7510.

Prerequisites: 

CS6505 or CS6550

Course Text: 

No text

Topic Outline: 
  • Spanning Trees [Depth-first, breadth-first, minimum weight, Kruskal & Prim algorithms, greedy algorithm]
  • Shortest paths [Algorithms of Dijkstra, Bellman-Ford, Floyd-Warshall]
  • Matchings [Augmenting paths, bipartite matching, Hungarian method, minimum weight, Edmonds' theorem, Chinese postman, T-cuts, T-joins]
  • Network flows [max-flow min-cut, Hoffman's circulation theorem, Hu's 2-commodity flow theorem]
  • Connectivity [Vertex- and edge-disjoint paths, testing connectivity, decomposing connected graph into blocks, Tutte's decomposition, edge-connectivity, Gomory-Hu trees]
  • Coloring [Brooks and Vizing theorem, edge-coloring bipartite graphs, 5-coloring planar graphs]
  • Testing planarity [Kuratowski's theorem, planarity algorithm in quadratic time or better]
  • Directed graphs [Digraphs connectivity, decomposition into strong components, ear decomposition, Roy-Gallai theorem]
  • Tree width [Basics, linear-time algorithms for problems on graphs of bounded tree-width]