Grafové algoritmy

Přednáška z grafových algoritmů [NDMI010] se koná v ZS 2006/2007 v úterky od 12:20 v S3.

K přednášce průběžně vznikají skriptíčka.

datum co se přednášelo
10. 10. Toky v sítích: formulace, základní věty a Ford-Fulkersonův algoritmus.
17. 10. Přednáška se nekonala
24. 10. Převod bipartitního párování a k-souvislosti na toky v sítích. Königova a Mengerova věta coby snadné důsledky Ford-Fulkersonovy věty. Dinicův algoritmus a důkladná analýza různých jeho variant. Scalovací algoritmus pro celočíselné kapacity.
31. 10. Bipartitní párování a k-souvislost pomocí toků i bez nich. Perfektní párování v regulárním bipartitním grafu pomocí degree splittingu. Globální hranová k-souvislost (Nagamochi-Ibaraki) rekurzivně.
6. 11. Gomory-Hu Trees: Datová struktura pro efektivní popis všech minimálních řezů v grafu. Základní vlastnosti a algoritmus pro efektivní konstrukci.
13. 11. Minimální kostry: základní věty o struktuře MST. Červeno-modrý algoritmus a jeho dualita. Důkazy korektnosti všech klasických algoritmů zdarma.
20. 11. Minimální kostry v rovinných grafech a minor-closed třídách grafů (Borůvkův algoritmus s kontrakcemi a filtrováním). Chytrá a chytřejší implementace Jarníkova algoritmu pomocí Fibonacciho hald.
27. 11. Výpočetní modely. Počítání na RAMu (triky s bitovými operacemi a násobením; jak udělat z normálního procesoru vektorový). Van Emde-Boasovy stromy.
5. 12. Bitově paralelní B-stromy. Q-Heaps a minimální kostra pro celočíselné váhy hran v lineárním čase.
12. 12. Dokončení Q-Heaps z minulé přednášky. Techniky dekompozice stromů: clusterizace a micro/macro-tree dekompozice, problém stromových předchůdců a Union-Find problem s předem známou posloupností Unionů.
19. 12. Suffixové stromy, jejich vlastnosti a dva lineární algoritmy pro jejich konstrukci (rekurzivní a inkrementální). Převod řetězcových problémů na grafové.
9. 1. Testování rovinnosti grafů a kreslení grafů do roviny (Boyer-Myrvold 2004).

Zkoušky

Zkušební termíny jsou vypsány i v letním zkouškovém, zapisujte se, prosím, v SISu.

Zkoušet budu vše, co bylo odpřeneseno, mimo Ukkonenova inkrementálního algoritmu pro konstrukci suffixových stromů (ten jsme na přednášce pouze nastínili), technických detailů implementace Q-heapů a důkazu korektnosti rovinného kreslení.

Vše byste měli najít ve skriptíčkách, pokud naleznete jakoukoliv chybu nebo nepřesnost, uvítám, když mne na ni upozorníte (čím víc, tím lépe :)).

Literatura

Stránku spravuje Martin Mareš