# Course Details for A.Y. 2013/2014

#### Name:

**Progetto e Ottimizzazione di Reti / Network Flows**

### Basic information

##### Credits:

*:* Laurea Magistrale in Informatica 6 CFU (c)

##### Degree(s):

Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio

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

### 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: 19 febbraio 2014, 14:50*