Grafové algoritmy

V zimním semestru 2008/2009 vedu přednášku z Grafových algoritmů. Bude se konat každou středu od 14:00 v S5.

datum co se přednášelo
8. 10. Toky v sítích: formulace, základní věty a Fordův-Fulkersonův algoritmus.
15. 10. Převod k-souvislosti na toky v sítích, Mengerova věta a související algoritmické úlohy. Dinicův algoritmus a důkladná analýza jeho všelijakých variant.
22. 10. Pokračování rozboru Dinicova algoritmu pro speciální sítě. Škálovací algoritmus pro celočíselné kapacity. Perfektní párování v regulárním bipartitním grafu pomocí redukce stupňů (pozor, v tištěné verzi skriptíček je chyba, podívejte se do té na webu).
29. 10. Vrcholová a hranová souvislost grafu pomocí toků i bez nich (Nagamochi-Ibaraki). Úvod do minimálních koster.
5. 11. Minimální kostry: Základní věty o struktuře (lehké hrany a výměny). Červeno-modrý algoritmus a jeho dualita.
12. 11. Minimální kostry v rovinných grafech a minorově uzavřených třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Odhady hustoty minorově uzavřených tříd (Maderova věta s důkazem, Kostočkova-Thomasonova bez důkazu).
19. 11. Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald. Stručně o výpočetních modelech.
26. 11. Inkrementální udržování komponent souvislosti (Union-Find). Jak se problém změní, když předem víme, s jakým stromem skončíme? Dekompozice stromů (komprese cest, mikro-makro rozklad).
3. 12. Problém stromových předchůdců a problém intervalových minim. Van Emde-Boasovy stromy.
10. 12. Počítání na RAMu (triky s bitovými operacemi a násobením; jak udělat z normálního procesoru vektorový). Bitově paralelní B-stromy a úvod do Q-hald. Minimální kostra pro celočíselné váhy hran v lineárním čase.
17. 12. Q-haldy.
7. 1. Suffixové stromy, jejich vlastnosti a Kärkkainenův-Sandersův algoritmus pro jejich konstrukci v lineárním čase. Převod řetězcových problémů na grafové.
14. 1. Testování rovinnosti grafů a kreslení grafů do roviny (Boyer-Myrvold 2004).

Zkoušky

Zkouším každou středu ve zkouškovém období od 10:00 (přihlašte se, prosím, v SISu), pokud by se vám to více hodilo jindy, ozvěte se mi.

Ke zkoušce byste měli znát odpřednesené a umět to aplikovat. Slibuji, že nebudu zkoušet technické detaily Q-hald a důkaz věty o hustotě minorově uzavřených tříd :)

Literatura

Stránku spravuje Martin Mareš