Toky a cesty s omezením

• Thesis title in Czech: Toky a cesty s omezením
• Thesis title in English: Flows and cuts with restriction
• Key words: řez, sériově-paralelní grafy, algoritmus, složitost
• English key words: cut, series-parallel graphs, algorithm, complexity
• Academic year of topic announcement: 2011/2012
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. Mgr. Petr Kolman, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 08.11.2011
• Date of assignment: 09.11.2011
• Confirmed by Study dept. on: 16.11.2011
• Date and time of defence: 18.09.2012 10:00
• Date of electronic submission: 02.08.2012
• Date of submission of printed version: 03.08.2012
• Date of proceeded defence: 18.09.2012
• Opponents: Mgr. Marek Krčál, Ph.D.

Guidelines

Tématem práce budou toky a řezy v grafech a jejich vzájemný vztah v situacích,
kdy nějakým způsobem omezíme vlastnosti toku a řezu (např. přidáním omezení
na maximální možnou délku použitelných cest), případně zároveň omezíme třídu
grafů, na kterých toky a řezy vyšetřujeme. Úkolem diplomanta bude vypracovat
přehled o současném poznání v této oblasti (se zaměřením především na již
zmíněné toky a řezy s omezením na ďélku cest), pokusit se vystihnout, v čem
spočívá obtíž otevřených problémů z oblasti, a pokusit se některé alespoň částečně
vyřešit.

References

Knihy:
Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003
Vijay V. Vazirani: Approximation Algorithms, Springer-Verlag, Berlin, 2001.
David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

Odborný článek:
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman,
Ondřej Pangrác, Heiko Schilling and Martin Skutella: Length-Bounded Cuts and Flows
ACM Transactions on Algorithms, Volume 7, Issue 1, Article No. 4, 2010.