Notes - Pages 218-275

Chapter 8 discusses algorithms on graphs, run times, and representations (matrix vs adjaceny lists) which are covered in most undergraduate computer science curriculums. The betweeness algorithm that runs in $O(n^2)$ and Faugmenting Path Algorithm of Ford and Fulkerson were new topics.

maximum flow— Augmented Path algorthm uses BFS with a simulated flow, s.t. netflow of any path has to be 1 at the end and all paths are found. This gives you the number of independent paths between two nodes, the size of the minimum cut set, and the maximum flow since these are equivalent. With slight modifications the min cut set, and independent paths can be found.