Network Flows and Graphs (Spring 2012)

This website contains handouts, lecture notes, and other helpful material for the OA 4202 course, Network Flows and Graphs.

You are invited to read the class syllabus.

The Sakai forum for the class is an excellent place for students to discuss homework assignments and ask questions.

Homeworks

Class Projects

We had a number of outstanding projects this quarter, both technically, and in terms of analysis. Below are all the class projects, in alphabetical order by topic.

Lecture Videos

  1. Introduction to networks, and networks problems.  view online or download
  2. Review big-Oh, review data structures.  view online or download
  3. Describing graphs mathematically, storing graphs in a computer.  view online or download
  4. Storing graphs in a computer, definitions on graph structure.  view online or download
  5. Shortest path as LP, definitions on graph structure, breadth-first search.  view online or download
  6. Go over HW 0. view online or download
  7. Go over GAMS prep. view online or download
  8. BFS and DFS examples and properties. view online or download
  9. Detecting cycles, topological sort, strongly connected component. view online or download
  10. Dijkstra's algorithm. view online or download
  11. Critical path method, DAG shortest path. view online or download
  12. GAMS 0, A* search. view online or download
  13. Go over HW 1, unimodular constraint matrix. view online or download
  14. Overview of network models. view online or download
  15. Shortest path interdiction, shortest path dual. view online or download
  16. GAMS loops, Bender's decomposition for shortest path interdiction. view online or download
  17. Go over HW 2, introduce HW 3.1. view online or download
  18. Example of Bender's decomposition, max-flow problem. view online or download
  19. Max-flow min-cut theorem, introduction to Ford-Fulkerson algorithm. view online or download
  20. Go over HW 3.1, Ford-Fulkerson example. view online or download
  21. Ford-Fulkerson run time, applications of max-flow. view online or download
  22. Go over HW 3.2, discuss projects, max-flow interdiction. view online or download
  23. Max-flow interdiction, min-cost-flow problem. view online or download
  24. Production and transport planning, tracking moving objects. view online or download
  25. Tanker scheduling, network reliability. view online or download

Notes

  • Notes 1 -- Review big-Oh, data structures, graph terminology, storing graphs in a computer.
  • Notes 2 -- Intro to shortest path as an LP, graph search (BFS, DFS), applications of search.
  • Notes 3 -- Shortest path algorithms.
  • Notes 3.1 -- Overview of network models.
  • Notes 4 -- Interdicting shortest paths.
  • Notes 5 -- Maximum flow.
  • Notes 5.1 -- Interdicting max flow.
  • Notes 6 -- Minimum cost flow.
  • Nodes 7 -- Multi-commodity flow.
  • Notes 8 -- Constrained shortest path.
  • Notes 9 -- Network simplex algorithm.
This is a completed course

© Copyright 2004-2017 - Ned Dimitrov