Graph Theory and Network Flows (IE 512)

2021 Spring
Faculty of Engineering and Natural Sciences
Industrial Engineering(IE)
3
10.00
Amine Gizem Özbaygın ozbaygin@sabanciuniv.edu,
Click here to view.
English
Doctoral, Master
--
Formal lecture
Click here to view.

CONTENT

Theory and applications of graphs and networks; properties of graphs; Hamiltonian and Eulerian walk problems; Travelling salesman problem and variants; design and analysis of shortest path, maximum flow and minimum cost network flow algorithms; matching and assignment; network simplex algorithm.

OBJECTIVE

In this course, students will be exposed to various network flow problems. Mainly, applications, basic algorithms and strongly polynomial algorithms will be presented for each type of problem. This course may be interesting for industrial engineering, computer science and telecommunications engineering graduate students depending on their research interests.

LEARNING OUTCOME

Upon completion of this course, students should be able to:
Describe a problem by using graphs and/or networks as an abstract model.
Distinguish the main aspects of different network representation approaches.
Develop a network representation of the problem by using the abstract graph/network based model.
Among shortest path, maximum flow and minimum cost flow problems, identify the type of network flow problem to be solved for the network representation of the problem.
Analyze the computational complexity of the algorithms for network flow problems.
Compare the use of different data structures with respect to their effect on the complexity of the algorithms, and observe the theoretical and empirical differences among the complexities.
Associate graph-theoretic problems with their combinatorial structures.

ASSESSMENT METHODS and CRITERIA

  Percentage (%)
Final 35
Midterm 50
Homework 15

RECOMENDED or REQUIRED READINGS

Textbook

Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.

Readings

Aldous, Joan M., and Robin J. Wilson. Graphs and Applications: An Introductory Approach. Springer Science & Business Media, 2003.
Balakrishnan V. Network Optimization, Chapman and Hall, 1995.
Bertsekas, Dimitri P. Network Optimization: Continuous and Discrete Methods, Athena Scientific, 1998.
Bertsekas, Dimitri P. Linear Network Optimization: Algorithms and Codes, MIT Press, 1991.
Winston, Wayne L., and Jeffrey B. Goldberg. Operations Research: Applications and Algorithms, Duxbury Press, 2004.