Sylabus
Toky v sítích: Dinicův algoritmus, algoritmus Tří Indů, metody pro řídké sítě a sítě s celočíselnými kapacitami.
Testování k-souvislosti grafů: hledání řezů a separátorů pomocí toků, Kargerův-Steinův pravděpodobnostní algoritmus.
Nejkratší cesty: Obecné relaxační schéma, Dijkstrův algoritmus a datové struktury pro něj (haldy, jedno- a víceúrovňové přihrádky). Potenciálová redukce a na ní založené heuristiky. Algebraické souvislosti s násobením matic, Kleeneho algebry. Tranzitivní uzávěry a Seidelův algoritmus.
Minimální kostry: Fredmanův-Tarjanův algoritmus pro obecné grafy, Fredmanův-Willardův pro celočíselné váhy a speciální algoritmy pro rovinné grafy a minorově uzavřené třídy.
Techniky dekompozice stromů: clusterizace a micro/macro-tree dekompozice, problém stromových předchůdců a Union-Find problem.
Převod řetězcových problémů na grafové: suffixové stromy a jejich konstrukce v lineárním čase.
Testování rovinnosti grafů a konstrukce rovinných nakreslení.
Anotace
Obsah přednášky tvoří pokročilejší grafové algoritmy a techniky jejich návrhu.