Course info

Network flows: Applications, definitions, graphs, paths, trees, cycles, loops, walk, network representation (adjacency list and matrices) and basic network transformations; Network algorithms; Complexity, Search Algorithms, Strategies for designing polynomial algorithms. Shortest Path Algorithms: Label setting, Dijkstra’s and Dial’s algorithms, Optimality conditions, label correcting algorithms and optimality conditions, detecting negative cycles, allpair shortest path algorithms; preflow push polynomial time algorithms, capacity scaling techniques. Minimum cost network assignment: optimality conditions, cyclecanceling algorithm, Successive shortest path algorithm, other polynomial time variants; Network equilibrium analysis; principles and optimisation formulations, FrankWolfe algorithm; Special cases and variants. Applications: Applications of mincost, maxflow, and shortest path algor ithms to transportation and infrastructure networks: transportation networks, airline, freight, facility location, logist