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

diplomski rad

• Autor: Ana Klobučar
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Saša Singer (član povjerenstva)
• Član povjerenstva: Vedran Krčadinac (član povjerenstva)
• Član povjerenstva: Vjeran Hari (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2015-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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(n^2)\).

Sažetak (engleski)

In this work we discussed vertex cover problem. The vertex cover is subset of set of vertices such that each edge of graph is incident to at least one vertex of the cover. The problem is to find such minimal set. Unfortunately, the problem is NP-complete so we can not use exact algorithms but we can use approximation algorithms. In this work we described 3 approximation algorithms for the vertex cover problem. The first described algorithm is greedy algorithm based on idea of choosing the vertex with the maximum degree and removing all its incident edges at each step. Although the idea seems natural, turns out that algorithm is not so good because it has not constant approximation ratio. The second algorithm is very similar to the first one. The idea is next: choose arbitrary edge, add its edges to the cover and remove all adjacent edges. This algorithm has constant approximation ratio of 2. The third and last described algorithm is based on linear programming and primal-dual method. First we formulated our problem as the Standard Minimum problem and then we relaxed Dual Complementary Slackness. On this basis, we described approximation integer algorithm. This algorithm also has constant approximation ratio of 2. For all algorithms we gave pseudocode and implementation. Also, we proved statements about their approximation ratios and analyzed time complexity. We showed that all algorithms have a running time of \(O(n^2)\).

• Ključne riječi: vršni pokrivač grafa; minimalni pokrivač; aproksimacijski algoritmi; pohlepni algoritam; linearno programiranje; primal-dual metoda
• Ključne riječi (engleski): vertex cover; minimal vertex cover; approximation algorithms; greedy algorithm; linear programming; primal-dual method
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:131882
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Pristup korisnicima matične ustanove
• Datum i vrijeme pohrane: 2019-02-13 11:28:34