prikaz prve stranice dokumenta Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa
Access restricted to students and staff of home institution
master's thesis
Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa
Zagreb: University of Zagreb, Faculty of Science, 2015. urn:nbn:hr:217:131882
Klobučar, Ana
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Klobučar, A. (2015). Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:131882

Klobučar, Ana. "Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa." Master's thesis, University of Zagreb, Faculty of Science, 2015. https://urn.nsk.hr/urn:nbn:hr:217:131882

Klobučar, Ana. "Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa." Master's thesis, University of Zagreb, Faculty of Science, 2015. https://urn.nsk.hr/urn:nbn:hr:217:131882

Klobučar, A. (2015). 'Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa', Master's thesis, University of Zagreb, Faculty of Science, accessed 10 July 2024, https://urn.nsk.hr/urn:nbn:hr:217:131882

Klobučar A. Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2015 [cited 2024 July 10] Available at: https://urn.nsk.hr/urn:nbn:hr:217:131882

A. Klobučar, "Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2015. Available at: https://urn.nsk.hr/urn:nbn:hr:217:131882

Metadata
TitleAproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa
AuthorAna Klobučar
MentorGoranka Nogo (mentor)
Committee memberGoranka Nogo (predsjednik povjerenstva)
Committee memberSaša Singer (član povjerenstva)
Committee memberVedran Krčadinac (član povjerenstva)
Committee memberVjeran Hari (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2015-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:131882
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2019-02-13 11:28:34