čtvrtek 16. března 2017

Pražský informatický seminář

Dvacátésedmé setkání Pražského informatického semináře
proběhne 23. března 2017
v posluchárně S5, MFF UK,
Malostranské nám. 25, Praha 1.

Na programu je Monika Henzinger: Hledání globálně minimálních řezů: Toky v sítích vs. PageRank
Monika Henzinger(foto)
Anotace:

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.

Bližší informace najdete na webové stránce PIS.

Žádné komentáře:

Okomentovat