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
(1 + α) ∑u ∈ (P1 ∩ P2) r(u) + ∑u ∈ (P1 ∩ P2), r(u) < 0 r(u) + ∑u ∈ (P1 ∪ P2) − (P1 ∩ P2) r(u) , kde r(u) je skóre vrcholu u.
Chceme efektívne nájst dvojicu ciest P_1, P_2 s najväčším 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
Repozitár