# Course Details for A.Y. 2015/2016

#### Name:

**Network Flows / Network Flows**

### Basic information

##### Credits:

*:* Master Degree in Computer Science 6 CFU (c)

##### Language:

English

### 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
* *

### 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*