Syllabus Application
IE 512
Graph Theory and Network Flows
Faculty
Faculty of Engineering and Natural Sciences
Semester
Spring 2025-2026
Course
IE 512 -
Graph Theory and Network Flows
Time/Place
Time
Week Day
Place
Date
11:40-12:30
Tue
FENS-L030
Feb 16-May 22, 2026
11:40-13:30
Thu
FASS-1075
Feb 16-May 22, 2026
Level of course
Masters
Course Credits
SU Credit:3, ECTS:10
Prerequisites
-
Corequisites
-
Course Type
Lecture
Instructor(s) Information
Duygu Taş Küten
- Email: duygu.tas@sabanciuniv.edu
Course Information
Catalog Course Description
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.
Course Learning Outcomes:
| 1. | Upon completion of this course, students should be able to: Describe a problem by using graphs and/or networks as an abstract model. |
|---|---|
| 2. | Distinguish the main aspects of different network representation approaches. |
| 3. | Develop a network representation of the problem by using the abstract graph/network based model. |
| 4. | 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. |
| 5. | Analyze the computational complexity of the algorithms for network flow problems. |
| 6. | 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. |
| 7. | Associate graph-theoretic problems with their combinatorial structures. |
Course 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, and Computer Science and Engineering graduate students depending on their research interests.
-
Course Materials
Resources:
Recommended Textbook: Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory,
Algorithms and Applications. Prentice-Hall.
Supplementary Reading Material:
• Aldous, J.M., and Wilson, R.J. (2003). Graphs and Applications: An Introductory Approach.
Springer Science & Business Media.
• Balakrishnan, V. (1995). Network Optimization. Chapman and Hall.
• Bertsekas, D.P. (1998). Network Optimization: Continuous and Discrete Methods. Athena
Scientific.
• Bertsekas, D.P. (1991). Linear Network Optimization: Algorithms and Codes. MIT Press.
• Winston, W.L., and Goldberg, J.B. (2004). Operations Research: Applications and
Algorithms. Duxbury Press.
Algorithms and Applications. Prentice-Hall.
Supplementary Reading Material:
• Aldous, J.M., and Wilson, R.J. (2003). Graphs and Applications: An Introductory Approach.
Springer Science & Business Media.
• Balakrishnan, V. (1995). Network Optimization. Chapman and Hall.
• Bertsekas, D.P. (1998). Network Optimization: Continuous and Discrete Methods. Athena
Scientific.
• Bertsekas, D.P. (1991). Linear Network Optimization: Algorithms and Codes. MIT Press.
• Winston, W.L., and Goldberg, J.B. (2004). Operations Research: Applications and
Algorithms. Duxbury Press.