Student Računarskog fakulteta Aleksa Plavšić je 29. septembra 2020. godine odbranio diplomski rad na temu „Problem pronalaženja najdužeg puta u neusmerenim netežinskim grafovima“ pred komisijom koju su činili: mentor dr Dragan Urošević i član dr Irena Jovanović.
„U ovom diplomskom radu je opisan problem pronalaženja najdužeg puta u neusmerenim netežinskim grafovima. Kako problem spada u grupu NP-teških, predstavljeno je nekoliko nepolinomijalnih algoritama različitih složenosti za grafove opšte strukture. Obrađene su pojedine klase grafova specijalne strukture za koje su pronađeni polinomijalni algoritmi poput stabala, kaktus grafova i blok grafova. Većina algoritama je zasnovana na pohlepnom pristupu i dinamičkom programiranju. Na kraju rada prodiskutovani su pojedini aproksimativni algoritmi iz ove oblasti, kao i ocene kvaliteta rešenja koje oni pronalaze.“ – navedeno je u apstraktu.
„Iako je problem aktivno izučavan prethodnih decenija, prostor za dalji napredak i doprinos postoji. Pored proučavanja materijala i oblasti koje ovom prilikom nismo obradili, dalje istraživanje biće zasnovano na pokušaju pronalaska polinomijalnog rešenja za neku od do sada neistraženih klasa grafova. Kao rezultat očekujemo da se iskristališu precizni ili aproksimativni algoritmi koji će uvesti nove granice ili poboljšati neke od postojećih. Takva otkrića bi najverovatnije dovela do osmišljavanja rešenja i za druge probleme slične prirode i dala povod za nove pokušaje dokaza jednakosti između skupova NP i P.“ – zaključio je Aleksa.
Fotografije sa odbrane nalaze se u galeriji.