SYST 420  / SYST 521

 Network Analysis

George Mason University

Fall 2009

                   Instructor: Ursula Morris                         Class Room: Robinson Hall A 247

                       Class Time: Fr. 1:30 - 4:10                        Office Hours: after class and by appointment



 Course Description

This course introduces network flow problems. These problems arise in many fields like computer networking, engineering, scheduling and routing, transportation, telecommunications. The course provides information about the theory, algorithms, and applications of network flow problems. The focus will be on shortest paths, maximum flow, minimum cost flow, and the network simplex algorithm.

The course begins with network nomenclature and elementary graph theory. This is followed by an introduction into data structures, complexity theory and flow decomposition. Based on these concepts shortest paths algorithms and the maximum flow algorithms are presented. A lecture on minimum spanning trees prepares for the following topics. A minimum cost network flow algorithm and a network simplex algorithm complete the basic topics of the course. As time permits, other topics might be added to the syllabus.

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

Software: During the course, a software package called MPL will be used. A free student version can be obtained by going to,, downloading the student version, and requesting an activation code asap.

Every student is expected to give two short presentation in class.

Course Topics (tentative)

1 Introduction and Network Terminology
2 Network Representations
3 Network Transformations
4 Complexity
5 Data Structures
6 Search Algorithms
7 Flow Decomposition
8 Shortest Path Algorithms
9 Max Flow Algorithms
10 Midterm
11 Minimum Spanning Trees
12 Minimum Cost Network Flows
13 Network Simplex
14 Additional Topics
15 Final Exam

Grading SYST 420:

Homework 20%
Midterm 35%
Presentations 10%
Final exam 35%