Course Details for A.Y. 2018/2019
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