Hledání globálně minimálních řezů: Toky v sítích vs. PageRank

V přednášce podáme přehled historie a současného poznání algoritmů pro hledání minimálních řezů v grafech, včetně některých nových výsledků. Zaměříme se na globálně minimální řezy, což je minimum z s-t řezů přes všechny dvojice vrcholů s a t. Je dobře známo, že cena minimálního s-t řezu v grafu je rovna velikosti maximálního toku z s do t, a standardní algoritmus pro počítání minimálního s-t řezu je skutečně založen na výpočtu maximálního toku. Pro globálně minimální řezy však stejný přístup vede k neefektivnímu algoritmu, který vyžaduje výpočet n maximálních toků, kde n je počet vrcholů grafu.

Do nedávné doby nejrychlejší algoritmus pro globálně minimální řezy v nevážených grafech proto nepoužíval výpočty toků, ale namísto toho spoléhal na opakované výpočty míry PageRank v kombinaci s různými grafově-teoretickými úvahami. Vysvětlíme, jak nahradit výpočty PageRank výpočty toků s více zdroji a více s toky, což vede k nejrychlejšímu současnému algoritmu pro výpočet globálně minimálních řezů v nevážených grafech. Spoluautory výsledků jsou Satish Rao a Di Wang.