Семинар Катедре за рачунарство и информатику, 12. април 2018.

Наредни састанак Семинара биће одржан у четвртак, 12. априла 2018. у сали 718 Математичког факултета са почетком у 18:15 часова.

Предавач: др Александар Картељ

Наслов предавања: ПАРТИЦИОНИСАЊЕ РЕТКИХ БИОЛОШКИХ МРЕЖА НА K-PLEX ПОДМРЕЖЕ

Апстракт: У мрежи, k-plex представља подскуп од n чворова такав да је је степен сваког чвора подмреже индуковане тим подскупом чворова најмање n-k. Проблем k-plex максималног тежинског партиционисања по гранама (Маx-EkPP) је NP-тежак проблем који подразумава проналажење k-plex партиционисања улазне мреже таквог да је сума тежина свих грана у добијеним индукованим k-plex подмрежама максимална. Решавање Max-EkPP има значајну улогу у откривању нових информација у великих ретким биолошким мрежама. У раду је представљена метода променљивих околина (енгл. variable neighborhood method - VNS) за решавање проблема Max-EkPP. Експериментална тестирања су извршена над реалним метаболичким мрежама и над другим доступним тест скуповима из литературе. Предложена VNS метода потврђује сва оптимална решења добијена моделом целобројног линеарног програмирања. За сва остала решења из литературе, за која не постоји потврда оптималности, VNS или достиже најбоље познато решење или га побољшава. VNS је такође тестиран над тест проблемима великих димензија који претходно нису разматрани у литератури.


Оставите ваш коментар:


(опционо)
(неће бити приказано)



Вести и дешавања


Активности на семинарима

све вести