Délkově omezené řezy v grafech
| Thesis title in Czech: | Délkově omezené řezy v grafech |
|---|---|
| Thesis title in English: | Length bounded cuts in graphs |
| Key words: | řez, rovinný graf, stromová šířka, dynamické programování |
| English key words: | cut, planar graph, tree width, dynamic programming |
| Academic year of topic announcement: | 2018/2019 |
| 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: | 26.03.2019 |
| Date of assignment: | 26.03.2019 |
| Confirmed by Study dept. on: | 09.04.2019 |
| Date and time of defence: | 16.09.2019 09:00 |
| Date of electronic submission: | 19.07.2019 |
| Date of submission of printed version: | 19.07.2019 |
| Date of proceeded defence: | 16.09.2019 |
| Opponents: | Mgr. Pavel Dvořák, Ph.D. |
| Guidelines |
| Řezy a toky v grafech a jejich různé varianty patří mezi důležité objekty zájmu kombinatorické optimalizace. Jednou variantou jsou i tzv. toky a řezy omezené délky. Pro daný graf G, jeho dva vrcholy s a t a celočíselný parametr L, L-omezený tok je takový tok v grafu G mezi vrcholy s a t, který je dekomponovatelný na cesty délky nejvýšše L, a L-omezený řez je podmnožina hran grafu G taková, že po jejím odstranění neexistuje mezi s a t cesta délky L nebo kratší. Problém nalezení L-omezeného řezu mimální velikosti je NP-težký.
Úkolem diplomanta bude následující: vypracovat přehled známých výsledků a otevřených problémů souvisejících s L-omezeným řezem, včetně stručného rozboru (ne)použitelnosti známých technik návrhu aproximačních algoritmů pro tento problém; pokusit se zjednodušit algoritmus a jeho analýzu pro L-omezený tok na grafech omezené stromové šířky; případně analyzovat tzv. celočíselnou propast (integrality gap) nové LP relaxace pro L-omezený tok na grafech, na kterých je klasická LP relaxace slabá. |
| 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. Odborné články: 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. P. Dvořák and D. Knop. Parametrized complexity of length-bounded cuts and multi-cuts. In Proc. of 12 Annual Conference on Theory and Applications of Models of Computation (TAMC), str. 441–452, 2015. E. Chlamtáč, P. Kolman. L-bounded Cut and Triangle Inequalities. Nepublikovaný manuskript. 2018. |