Seminář z grafových algoritmů
V LS 2012/2013 se budeme zabývat především algoritmy pro toky v sítích. Zápočet se uděluje za aktivní účast a přednesení referátu.
Seminář se koná každé úterý od 9:00 v S10.
Program semináře
| datum | referuje | téma |
|---|---|---|
| 26. 2. | Domluva na programu semináře. Link-Cut Trees a zrychlení Dinicova algoritmu. | |
| 5. 3. | Martin Mareš | D. D. Sleator, R. E. Tarjan: A Data Structure for Dynamic Trees |
| 12. 3. | Pavel Taufer | R. K. Ahuja, J. B. Orlin, R. E. Tarjan: Improved Time Bounds for the Maximum Flow Problem |
| 19. 3. | Jan Musílek | S. W. Bent, D. D. Sleator, R. E. Tarjan: Biased Search Trees |
| 26. 3. | Jan Musílek | (pokračování z minula) |
| 2. 4. | Karel Tesař | J. Cheriyan, T. Hagerup, K. Mehlhorn: Can a Maximum Flow be Computed in o(nm) Time? |
| 9. 4. | Lucie Mohelníková | V. King, S. Rao, R. Tarjan: A Faster Deterministic Maximum Flow Algorithm |
| 16. 4. | Pavel Veselý | (pokračování z minula) |
| 23. 4. | Ladislav Láska | J. B. Orlin: Maximum Flows in O(nm) time, or better |
| 30. 4. | Adam Juraszek | G. Borradaile, P. Klein: An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph |
| 7. 5. | Seminář se nekoná, je Jarní škola. | |
| 14. 5. | Jitka Novotná | W. Schnyder: Embedding Planar Graphs on the Grid |
| 21. 5. | Michal Dzetkulič | S. Pettie, P. Sanders: A simple linear-time 2/3-ε approximation for maximum weight matching |