Network Flows and Graphs (Fall 2010)

This page contains the course materials for Network Flows and Graphs, OA4202.

The sidebar contains the class calendar.  The calendar simply lists relevant dates for exams and homework assignments.

You are also invited to read the class syllabus.

Lecture Contents

Here, we list the lecture contents.

  1. Introduction.  Describing graphs mathematically.  Storing graphs in a computer.
  2. Storing graphs in a computer.  Definitions on graph structure.  Breadth First Search.
  3. Go over homework 0.  Properties of breadth first search.  Depth first search.
  4. Properties of depth first search.  Identifying a cycle.  Topological sort.  Strongly connected component.
  5. Go over homework 1.  Development of Dijkstra's algorithm.
  6. Properties of Dijkstra's algorithm.  A* search.  Shortest path in directed acyclic graphs.
  7. Bellman-Ford algorithm for shortest path with negative edge lengths.  Shortest path as an LP.
  8. Exam 0
  9. Go over HW2.  Introduce HW3.
  10. Shortest path as an LP.  Interdicting shortest paths: going from a max min to a max max.
  11. Interdicting shortest paths: row generation algorithm.  Floyd-Warshall for all pairs shortest paths.
  12. Introduction to Max Flow.  Dual of Max Flow and Max Flow Min Cut theorem.  Ford-Fulkerson algorithm.
  13. Determining optimal primal/dual variables from Ford-Fulkerson.  Ford-Fulkerson run time analysis.
  14. Capacity Scaling algorithm and analysis.  Producer/Consumer max flow.  Max flow with lower bounds.
  15. Minimizing number of ships to satisfy a schedule.  Network reliability and edge/node disjoint paths.
  16. Job selection to maximize profit.  Intro to minimum cost flow.  Network transformations.
  17. Applications of minimum cost flow.  Production planning and transportation.  Matching.
  18. Network transformations. Successive shortest path algorithm.
  19. Go over HW 5.  Modeling using minimum cost flows.
  20. Examples.

Homework Assignments

Lecture Notes

These are some hand written notes on the lecture material:

  • Notes 1.  Introduction to graphs.
    • Describing graphs mathematically.
    • Storing graphs in the computer.
  • Notes 2.  Search algorithms.
    • Definitions on graph structure.
    • Breadth first search.
    • Depth first search.
    • Identifying a cycle.
    • Topological sort.
    • Finding strongly connected component.
  • Notes 3.  Shortest path algorithms.
    • Dijkstra's algorithm
    • A* search
    • Directed acyclic graph shortest path
    • Bellman-Ford algorithm
  • Notes 4.  Shortest path as an LP.  Interdicting shortest path.
  • Notes 5.  All pairs shortest paths.  Floyd Warshall.
  • Notes 6.  Maximum flow.
  • Notes 6.1.  Addendum to notes 6, two more maximum flow applications.
  • Notes 7.  Minimum cost flow.
  • Notes 7.1.  Successive Shortest Path algorithm.

© Copyright 2004-2019 - Ned Dimitrov