Network Optimization
Problem set 3
- Introduction to network models
- Computational complexity and data structures
- Graph search algorithms
- Transformations and flow decomposition
- Shortest paths: label setting algorithms
- The radix heap algorithm
- Shortest paths: label correcting algorithms
- Algorithm analysis
- Basic algorithms for the maximum flow problem
- Combinatorial applications of maximum flows
- Preflow push algorithms
- More on preflow push algorithms
- Minimum cost flow: basic algorithms
- Minimum cost flow: polynomial time algorithms
- Applications of network flows; Linear programming review
- The network simplex algorithm
- Lagrangian relaxation 1
- Lagrangian relaxation 2
- Multicommodity flows 1
- Multicommodity flows 2
- Breadth first search
- Depth first search
- Topological ordering
- Eulerian cycles in directed graphs
- Flow decomposition
- Dijkstra's algorithm
- Dial's algorithm
- 2-level bucket algorithm
- Radix heap animation
- Label correcting algorithm
- Modified label correcting algorithm
- Ford-Fulkerson algorithm
- Preflow push algorithm
- Negative cycle (cycle canceling) algorithm
- Successive shortest path (SSP) algorithm
- Network simplex animations
