Seminář z grafových algoritmů
V LS 2009/2010 bude mít seminář formu zčásti přednášky, zčásti referativního semináře. Téma se bude točit okolo nejkratších cest a datových struktur.
Scházíme se v pátek od 9:00 v S6.
Co jsme dělali
| datum | kdo | téma |
|---|---|---|
| 5. 3. | Martin Mareš | Úvod do nejkratších cest. Základní algoritmy: scanovací meta-algoritmus, Bellman-Ford, Dijkstra, Floyd-Warshall. Potenciálová redukce pro odstranění záporných hran. Využití znalosti cíle: obousměrný Dijkstra, A* (a jeho souvislost s potenciály) a algoritmus s majáky. |
| 12. 3. | Martin Mareš | Rekurzivní kvantování pro celočíselné délky hran. Využití planárních separátorů pro APSP v rovinných grafech (jednoduchý algoritmus v čase O(n2.5). APSP a (+,min)-součiny matic; jak se zbavit logaritmů. Seidelův algoritmus pro APSP v neohodnocených neorientovaných grafech. |
| 19. 3. | — | Seminář odpadá (Jarní Škola Kombinatoriky) |
| 26. 3. | — | Seminář odpadá (Celostátní kolo MO-P) |
| 2. 4. | Martin Mareš | Celočíselné datové struktury: simulace vektorových operací pomocí aritmetiky na RAMu. Q-haldy. |
| 9. 4. | Martin Mareš | Všehochuť o počítání v pointerových modelech. Malé nahlédnutí do zoo složitostních tříd. |
| 16. 4. | Vojta Tůma | S. Chaudhuri, C.D. Zaroliagis: Shortest Paths in Digraphs of Small Treewidth, Sequential Algorithms |
| 23. 4. | Michal Vaner | Monika R. Henzinger: Faster shortest-path algorithms for planar graphs |
| 30. 4. | Michal Kozák | Mikkel Thorup, Uri Zwick: Approximate Distance Oracles |
| 7. 5. | — | Seminář odpadá (Soustředění KSP) |
| 14. 5. | Anna Bernáthová | B. V. Cherkassky, A. V. Goldberg: Heap-on-Top Priority Queues |
| 21. 5. | Radek Hušek | Mikkel Thorup: Undirected SSSP with Integer Weights in Linear Time |