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

                        Email: [email protected]

 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 http://www.maximalsoftware.com,, downloading the student version, and requesting an activation code asap.

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

Course Topics (tentative)

Grading SYST 420: