Názov projektu: Najdrahšia dvojica ciest v orientovanom acyklickom grafe
Špecifikácia projektu: Máme daný orientovaný acyklický graf s ováhovanými vrcholmi. Skóre ciest P_1, P_2 je dané ako
∑u ∈ P_1 ∪ P_2 c(u) + α · ∑u ∈ P_1 ∩ P_2 c(u) ; kde c(u) je váha vrcholu u a α ∈ (0, 1)
Dostaneme vrcholy A, B a chceme nájsť dvojicu ciest P_1, P_2, kde P_1 aj P_2 idú z A do B a spomedzi všetkých takýchto ciest majú najväčšie skóre. Cieľom ročníkového projektu bude nájsť, dokázať a implementovať nejaké efektívne algoritmy na riešenie tohto problému. Tento problém má aplikácie v biológii, teda sa budeme snažiť nájsť a implementovať aj prakticky efektívne algoritmy pre skutočné dáta. Ako prvé sa budem zaoberať formuláciou a riešením tohto problému cez minimum-cost flow.Študent: Martin Madzin - madzin2@uniba.sk
Školiteľ: doc. Mgr. Bronislava Brejová, PhD. - brejova@dcs.fmph.uniba.sk