Toky cestami omezené délky
| Thesis title in Czech: | Toky cestami omezené délky |
|---|---|
| Thesis title in English: | Flows Along Paths of Bounded Length |
| Key words: | toky omezené délky, kombinatorická optimalizace, polynomiální algoritmus |
| English key words: | length-bounded flows, combinatorial optimization, polynomial algorithm |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | Bachelor's 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: | 05.02.2018 |
| Date of assignment: | 05.02.2018 |
| Confirmed by Study dept. on: | 12.02.2018 |
| Date and time of defence: | 06.09.2018 09:00 |
| Date of electronic submission: | 19.07.2018 |
| Date of submission of printed version: | 20.07.2018 |
| Date of proceeded defence: | 06.09.2018 |
| Opponents: | RNDr. Ondřej Pangrác, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |