hrvatski

Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa

U ovom diplomskom radu obrađen je problem vršnog pokrivača grafa. Vršni pokrivač grafa je podskup skupa vrhova takav da je svaki brid grafa incidentan s barem jednim vrhom pokrivača. Problem se sastoji od traženja minimalnog pokrivača. Nažalost, problem je NP-potpun pa ne možemo koristiti egzaktne algoritme već koristimo aproksimacijske. U radu su opisana 3 aproksimacijska algoritma za njegovo rješavanje. Prvi algoritam koji smo opisali je pohlepni algoritam koji se temelji na ideji da u svakom koraku uzmemo vrh najvećeg stupnja i uklonimo sve incidente bridove. Iako je ideja vrlo prirodna, ipak se pokaže da algoritam nije toliko dobar jer nema konstantni aproksimacijski faktor. Drugi algoritam je vrlo sličan prvome. Ideja je sljedeća: uzmi proizvoljan brid, dodaj njegove vrhove u pokrivač i ukloni susjedne. Ovaj algoritam pak ima konstantni aproksimacijski faktor koji iznosi 2. Treći i posljednji algoritam koji smo opisali se temelji na linearnom programiranju i primal-dual metodi. Prvo smo naš problem zapisali u formi minimizacijskog problema te smo relaksirali dualni uvjet oslabljenje komplementarnosti. Na temelju toga smo dali aproksimacijski cjelobrojni algoritam. Ovaj algoritam također ima aproksimacijski faktor 2. Za svaki od algoritama smo dali pseudokod te ga implementirali. Također smo dokazali tvrdnje o njihovim aproksimacijskom faktorima i analizirali vremensku složenost. Pokazali smo da je vremenska složenost svih algoritama O(n2).

minimalni vršni pokrivač grafa ; pohlepni algoritam ; linearno programiranje ; primal-dual metoda

nije evidentirano