SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
Flows, Paths and Cuts - NDMI067
Title: Toky, cesty a řezy
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. Mgr. Petr Kolman, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: T_KAM (21.04.2016)
Multicommodity flows genaralize in a natural way the classical flow problem: instead of just a single source- destination pair, there are several such pairs but there is still just one network and all flows must fit in it. Multicommodity flows and their dual cut problems are extremely useful in the design of approximation algorithms for many different graph problems. The lecture will provide an overview of the most important result in this area. The course is taught once in two years.
Course completion requirements -
Last update: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)

The exam is oral. The requirements correspond to the syllabus as covered by the lectures.

Literature -
Last update: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)

[1] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, (available online)

[2] V. Vazirani: Approximation Algorithms

Syllabus -
Last update: G_I (08.06.2007)

Multicommodity flows are a natural generalization of the classical flow: instead of just a single source-sink pair, there are k such pairs. The objective is (e.g.) to maximize the sum of the flows for all k commodities subject to the capacity constraints. The multicommodity flows and their dual cut problems received a lot of attention in the last decade. The aim of the lecture is present the most important results from this area and to demonstrate on them general approaches useful for design of approximation algorithms for NP-hard problems.

Charles University | Information system of Charles University |