Grafové algoritmy

V zimním semestru 2009/2010 vedu přednášku z Grafových algoritmů. Bude se konat každé úterý od 15:40 v S4.

datum co se přednášelo
6. 10. Toky v sítích: formulace, základní věty a Fordův-Fulkersonův algoritmus. Převod k-souvislosti na toky v sítích, Mengerova věta a související algoritmické úlohy.
13. 10. Toky v sítích: Dinicův algoritmus a důkladná analýza jeho všelijakých variant. Škálovací algoritmus pro celočíselné kapacity.
20. 10. Minimální řez v neorientovaných grafech bez použití toků (Nagamochi-Ibaraki). Perfektní párování v regulárním bipartitním grafu pomocí redukce stupňů, souvislost s hranovým barvením.
27. 10. Minimální řez pravděpodobnostně (Karger-Stein). [Dopsal jsem o něm novou kapitolu do skriptíček.]
3. 11. Minimální kostry: Základní věty o struktuře (lehké hrany a výměny). Červeno-modrý algoritmus a jeho dualita.
10. 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).
[Není ve skriptíčkách, ale podívejte se do mé disertace, kapitola 3.1.]
24. 11. Minimální kostry ještě jednou: Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald. Stručně o výpočetních modelech.
1. 12. Dekompozice problémů: stromoví předchůdci (LCA) a intervalová minima (RMQ). Union-Find a jeho verze s předem známým stromem Unionů. Mikro-/makro-stromy a komprese cest.
8. 12. 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é.
15. 12. Datová struktura pro dynamické udržování komponent souvislosti (Holm-de Lichtenberg-Thorup).
[Není ve skriptíčkách, najdete ji v kapitolách 5.2 a 5.3 disertace.]
5. 1. Testování rovinnosti grafů a kreslení grafů do roviny. Předehra: hledání mostů a artikulací prohledáváním do hloubky.
12. 1. Kreslení grafů do roviny a hledání nerovinných minorů. Zákusek: Van Emde-Boasovy stromy.

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. Rozbor případů v důkazu algoritmu na rovinné kreslení zkouším pouze na přání ;)

Literatura

Stránku spravuje Martin Mareš