Martina Šimůnková
Pondělí 10. listopadu 2014, 14:20 hodin
Místnost G4-MAT, 4. patro budovy G, kampus Husova (Univerzitní nám. 1410/1)
[Pozvánka v PDF]
Anotace
Mnoho grafových algoritmů lze přirozeným způsobem řešit jako úlohu lineární optimalizace. Méně samozřejmý je opačný proces, tedy zpětný překlad pojmů lineární optimalizace do řeči grafových algoritmů.
My si tento překlad ukážeme na příkladu algoritmu hledání nejlacinějšího perfektního párování v grafu. Z časových důvodů se omezíme na bipartitní grafy a v závěru naznačíme odlišnosti v obecném případě.
