Network Optimization
Course Name:
Network Optimization (CS834)
Programme:
M.Tech (CSE)
Category:
Elective Courses (Ele)
Credits (L-T-P):
03 (3-0-0)
Content:
Introduction, Mathematical preliminaries, Comparison of Label Setting and Label Correcting shortest path algorithms, Single Origin/Single Destination and Multiple Origin/Multiple Destination shortest path methods. The Max-Flow Problem: Cuts in a Graph, The Max-Flow/Min-Cut Theorem, The Maximal and Minimal Saturated Cuts, Price-Based Augmenting Path Algorithms. Multicommodity Flow Problems. Auction Algorithms for Min-Cost Flow: The Auction Algorithm for the Assessment Problem, Extensions of the Auction Algorithm, The Preflow-Push Algorithm for Max-Flow, The Auction/Sequential Shortest Path Algorithm. Simplex Methods for Min-Cost Flow.
References:
1.Ravindra K Ahuja, Thomas L. Magnanti, James B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993
2.Eugene Lawler, Combinatorial Optimization - Networks and Matroids, Dover Publication 2002
3. William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, Combinatorial Optimization, Wiley 1997
4.Michal Pioro, Deepankar Medhi, Routing Flow and Capacity Design in Communication and Computer Networks, The Morgan Kaufmann Series in Networkin.
Department:
Computer Science and Engineering