Math 466/566: Lecture Notes and Videos on Network Optimization
|
Copyright: I (Bala Krishnamoorthy) hold the copyright
for all lecture scribes/notes, documents, and other
materials including videos posted on these course web
pages. These materials might not be used for commercial
purposes without my consent.
|
Scribes from
all lectures so far (as a single big file)
| Lec | Date | Topic(s) | Scribe | Video |
| 1 |
Aug 25 |
syllabus,
the Konigsberg
bridges problem, Eulerian tour, shortest path (SP), max
flow (MF), and min cost flow (MCF) problems
|
Scb1
|
Vid1
|
| 2 |
Aug 27 |
MCF as optimization model, SP as MCF, MF as MCF: \((t,s)\)
with \(c_{ts}=-1,u_{ts}=\infty\), transportation
problem, seat-sharing problem
|
Scb2
|
Vid2
|
| 3 |
Sep 1 |
seat-sharing
problem, assignment problem, network definitions,
(in/out)degree, adjacency lists, induced and spanning subgraphs
|
Scb3
|
Vid3
|
| 4 |
Sep 3 |
walk, (directed) path, pred\((i)\), (strongly) connected,
(spanning) tree, cuts, node-arc incidence and node-node
adjacency matrices
|
Scb4
|
Vid4
|
| 5 |
Sep 8 |
forward star representation, (r)point
vector, Matlab
session and commands, network transformations:
removing lower bounds
|
Scb5
|
Vid5
|
| 6 |
Sep 10 |
arc reversal, removing upper bounds (gives bipartite
graph), node splitting, computational complexity:
algorithm running time
|
Scb6
|
Vid6
|
| 7 |
Sep 15 |
\(O(f(n)), \Omega(f(n)), \Theta(f(n))\) for running time and
functions, problem size, polynomial & exponential time algos,
generic search
|
Scb7
|
Vid7
|
| 8 |
Sep 17 |
video: breadth/dept-first search (BFS/DFS),
complexity of search: \(O(m)\), reverse search, strong
connectivity, topological order
|
Scb8
|
Vid8
|
| 9 |
Sep 22 |
topological order, indegree updates, \(O(m)\)
algorithm for topological order, flows along paths and
cycles, flow
decomposition
|
Scb9
|
Vid9
|
| 10 |
Sep 24 |
flow decomp theorem, shortest path (SP), assumptions,
bead-string model, knapsack as SP, UPDATE\((i)\) step,
Dijkstra's algorithm
|
Scb10
|
Vid10
|
Last modified: Thu Sep 24 23:21:29 PDT 2026
|