Select Academic Year:     2017/2018 2018/2019 2019/2020 2020/2021 2021/2022 2022/2023
First Semester 
Teaching style
Lingua Insegnamento

Informazioni aggiuntive

Course Curriculum CFU Length(h)
[60/73]  INFORMATICS [73/00 - Ord. 2017]  PERCORSO COMUNE 6 48


1. Knowledge and understanding skills.
The course is designed for the students of the 2nd year of the Master Degree in Computer Science.
This course aims to provide students with a deep knowledge in the theory and practice of network flows and its extensions. Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, and finance, as well as a number of other domains. This course will survey some of the applications of network flows and focus on key special cases of network flow problems such as the shortest path problem, the maximum flow problem, etc. The goals of the course are the following:
• To present the knowledge of the state-of-the-art in the theory and practice for solving network flow problems.
• To provide students with a rigorous analysis of network flow algorithms.
• To help each student develop his or her own intuition about algorithm development and algorithm analysis.
2. Ability to apply knowledge and understanding.
Students must apply what they learn in a course project, which is typically made with another student. They often choose projects of importance to the University of Cagliari or of personal interest to themselves.
3. Autonomy of judgment.
By facing realistic projects, students will be put in the position of critically thinking at the problem setting, evaluating which data are requested in their formulation, developing and running their algorithms, as well as and assessing the outcomes.
4. Communicative Skills.
s will enable students to develop the skills requested to present their work in an ordered and coherent way. Speaking skills will be evaluated in an oral interview, when projects will be presented. Communicative skills are further evaluated in the oral exam.
5. Learning Skills.
The course provides students with sufficient preparation to understand more advanced mathematical texts and makes them able to expand their knowledge autonomously in the future.


1. Knowledge. The course would benefit from a good understanding of the basic concepts of Linear Programming, which can be learned both in the Bachelor Degree Program and in the Master Degree Program.
2. Skill. Students must be able to read and understand Linear Programming models and pseudocodes.
3. Competences. The ability to use a Mixed Integer Programming solver is requested.
Prerequisite courses. None.


• Introduction to Network Flow Problems
• Paths, Trees and Cycles
• Algorithm Design and Analysis
• Algorithms for Shortest-Path problems
• Algorithms for Maximum-Flow problems
• The Minimum-Cost-Flow-Problem
• Multicommodity-flows

Teaching Methods

The course consists of 48 hours of lectures held in English. They cover theoretical concepts, as well as several exercises to review and reinforce the theoretical concepts. Finally, the professor provides regular support to students throughout the course by ad-hoc meetings and e-mails.

Verification of learning

Students must demonstrate their knowledge of the specific terminology, the ability to solve realistic problems and the theoretical concepts presented in the lectures. Students are evaluated in two stages: a project and an oral exam. The project must be approved by the Professor and is typically made in cooperation with another student. The conclusion of the project is a necessary condition to give the oral exam. Two questions are typically made in the oral exam. The answers are evaluated up to 12 points.
• The final mark ranges between 18/30 and 22/30 in the case of sufficient knowledge of the specific terminology, correct application of the methodological concepts and sufficient presentation of the concepts and results.
• The final mark ranges between 22/30 and 26/30 in the case of good knowledge of the terminology, good application of the methodological concepts and a good presentation of concepts and results.
• The final mark ranges between 27/30 and 30 cum laude in the case of an excellent mastery of specific terminology, a critical application of the methodological concepts and a clear display of concepts and results.
Students are advised to check their preparation during the lectures. They will test their skills by practicing with exercises and comparing their results to those presented by the Professor.


Ravindra k. Ahuja, Thomas L. Magnanti, James B. Orlin
Network Flows
Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.

More Information

The main teaching-supporting tool is the platform elearning platform (https://elearning.unica.it/), where additional information is available (e.g. a course diary reporting the topics of each lesson and further teaching files).

Questionnaire and social

Share on:
Impostazioni cookie