Algoritmy pro L-omezené toky
| Thesis title in Czech: | Algoritmy pro L-omezené toky |
|---|---|
| Thesis title in English: | Algorithms for L-Bounded Flows |
| Academic year of topic announcement: | 2015/2016 |
| Thesis type: | diploma thesis |
| Thesis language: | anglič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: | 26.04.2016 |
| Date of assignment: | 26.04.2016 |
| Confirmed by Study dept. on: | 03.05.2016 |
| Date and time of defence: | 08.06.2016 09:00 |
| Date of electronic submission: | 12.05.2016 |
| Date of submission of printed version: | 12.05.2016 |
| Date of proceeded defence: | 08.06.2016 |
| Opponents: | prof. RNDr. Luděk Kučera, DrSc. |
| Guidelines |
| Toky v grafech a jejich různé varianty patří mezi důležité objekty
zájmu kombinatorické optimalizace. Jednou dosud málo prozkoumanou variantou je i tzv. tok omezené délky. Jedná se o tok mezi dvěma vhrcholy, zdrojem a spotřebičem, který musí navíc splňovat požadavek na dekomponovatelnost na cesty délky nejvýšše L, kde L je parametr zadání. Maximální L-omezený tok je možno spočítat v polynomiálním čase optimálně pomocí lineárního programování, ale není znám žádný kombinatorický algoritmus, který by max. L-omezený tok spočítal bez použití lineárního programování jako pomocné procedury. Úkolem diplomanta bude prozkoumat, zda některý ze známých kombinatorických algoritmů pro obyčejný maximální tok, případně aproximací max. toku, je možno modifikovat pro výpočet max. L-omezeného toku. |
| 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á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. |