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

master's thesis

• Author: Ana Klobučar
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Saša Singer (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Vjeran Hari (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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)\).

Abstract (english)

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)\).

• Keywords: vršni pokrivač grafa; minimalni pokrivač; aproksimacijski algoritmi; pohlepni algoritam; linearno programiranje; primal-dual metoda
• Keywords (english): vertex cover; minimal vertex cover; approximation algorithms; greedy algorithm; linear programming; primal-dual method
• Language: croatian
• URN:NBN: urn:nbn:hr:217:131882
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Access restricted to students and staff of home institution
• Created on: 2019-02-13 11:28:34