Toky a cesty s omezením

• Název práce v češtině: Toky a cesty s omezením
• Název v anglickém jazyce: Flows and cuts with restriction
• Klíčová slova: řez, sériově-paralelní grafy, algoritmus, složitost
• Klíčová slova anglicky: cut, series-parallel graphs, algorithm, complexity
• Akademický rok vypsání: 2011/2012
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Mgr. Petr Kolman, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 08.11.2011
• Datum zadání: 09.11.2011
• Datum potvrzení stud. oddělením: 16.11.2011
• Datum a čas obhajoby: 18.09.2012 10:00
• Datum odevzdání elektronické podoby: 02.08.2012
• Datum odevzdání tištěné podoby: 03.08.2012
• Datum proběhlé obhajoby: 18.09.2012
• Oponenti: Mgr. Marek Krčál, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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.