Toky cestami omezené délky

• Název práce v češtině: Toky cestami omezené délky
• Název v anglickém jazyce: Flows Along Paths of Bounded Length
• Klíčová slova: toky omezené délky, kombinatorická optimalizace, polynomiální algoritmus
• Klíčová slova anglicky: length-bounded flows, combinatorial optimization, polynomial algorithm
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská 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í: 05.02.2018
• Datum zadání: 05.02.2018
• Datum potvrzení stud. oddělením: 12.02.2018
• Datum a čas obhajoby: 06.09.2018 09:00
• Datum odevzdání elektronické podoby: 19.07.2018
• Datum odevzdání tištěné podoby: 20.07.2018
• Datum proběhlé obhajoby: 06.09.2018
• Oponenti: RNDr. Ondřej Pangrác, Ph.D.

Zásady pro vypracování

Toky v grafech a jejich různé varianty patří mezi důležité objekty
zájmu kombinatorické optimalizace.

Tok omezené délky v grafu G je tok, který je dekomponovatelný na toky cestami
délky nejvýšše L, kde L je daný parametr problému. Pro danou dvojici vrcholů s
a t a parametr L je možné najít maximální L-omezený tok v polynomiálním čase
pomocí lineárního programování. Není ale znám žádný polynomiální kombinatorický
algoritmus (resp. algoritmus nezaložený na lineárním programování) pro tento
problém.

Úkol studentky bude dvojí.
1. Provést rešerši o problému L-omezeného toku a souvisejícím problému L-omezeného řezu.
2. Nastudovat článek The maximum k-flow in a network autorů V. Koubek a A.
Říha, publikovaný ve sborníku konference Mathematical Foundations of Computer
Science 1981, str. 389-397, a pokusit se doplnit chybějící důkazy několika
důležitých lemmat.

Seznam odborné literatury

Knihy:
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, a A. Schrijver.
Combinatorial Optimization, John Wiley and Sons, New York, 1998.

R. K. Ahuja, T. L. Magnati, J. B. Orlin. Network Flows: Theory,
Algorithms, and Applications, Pearson, 1993.

A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency,
Springer, 2003.

Odborné články:
Václav Koubek, Antonín Říha. The maximum k-flow in a network. Proceedings of
Mathematical Foundations of Computer Science 1981, 389-397, 1981.

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.

Diplomová práce:
Jan Voborník. Algoritmy pro L-omezené toky. MFF UK 2016.