Course Details for A.Y. 2018/2019

The information on this page refer to the academic year 2018/2019. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2018/2019

Name:

Network Flows / Network Flows

Type:

Module

Main course:

Network Design / Network design

Basic information

Code:

DT0059

Sector:

MAT/09

Credits:

: Master Degree in Computer Science 6 CFU (c)

Term:

2^nd semester

Degree(s):

Language:

English

Teacher(s):

Fabrizio Rossi

Same as:

Network Flows

Course Objectives

Ability to recognize and formulate network flow problems Knowledge of basic and advanced network flow algorithms Ability to design resolution approaches to solve non standard network flow problems

Course Content

Network Flows Problem: introduction and definitions
Maximum Flows and the path packing problem. Flows and cuts: Max-Flow/Min-Cut theorem. Augmenting path algorithms: Ford and Fulkerson algorithm, Edmonds and Karp algorithm. Generic Preflow-Push algorithm. Flows with lower bounds.
Maximum Flows: additional topics and applications. Flows in Unit Capacity Networks. Flows in Bipartite Networks. Network Connectivity.
Minimum Cuts. Global Minimum Cuts. Node Identification Algorithm. Random Contraction. Applications.
Minimum-Cost Flow Problems. Definition and applications. Optimality Conditions. The Ford-Bellman algorithm for the shortest path problem. Primal algorithms: Augmenting Circuit Algorithm for the Min Cost Flow Problem.
Network Simplex Algorithms. Applications of Min Cost Flows.

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Know and formulate network flow problems
Model decision problems as network flow problems Use base and advanced algorithms to solve network flow problems
Ability to identify network flow models scope
Ability to explain network flows models and algorithms
Ability to learn state-of-art algorithms for network flow problems

Prerequisites and Learning Activities

Basic knowledge of: Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity

Assessment Methods and Criteria

Written text exam

Textbooks

Cunningham, Pulleyblank, Schrijver , Combinatorial Optimization
Ahuja, Magnanti, Orlin, Network Flows

Internet Resources

Homepage:

http://www.di.univaq.it/rossi/networkdesign.html

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 28 gennaio 2016, 12:11