Klobučar, Ana (2015) Aproksimacijski algoritmi za traženje minimalnog vršnog pokrivača grafa. Diploma thesis, Faculty of Science > Department of Mathematics.
PDF
Restricted to Registered users only Language: Croatian Download (655kB)  Request a copy 

Archive
(dodatni materijali "kodovi")
Restricted to Registered users only Language: Croatian Download (4MB)  Request a copy 
Abstract
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 NPcomplete 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 primaldual 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)$.
Item Type:  Thesis (Diploma thesis) 

Supervisor:  Nogo, Goranka 
Date:  2015 
Number of Pages:  33 
Subjects:  NATURAL SCIENCES > Mathematics 
Divisions:  Faculty of Science > Department of Mathematics 
Depositing User:  Iva Prah 
Date Deposited:  20 Oct 2015 10:29 
Last Modified:  20 Oct 2015 10:29 
URI:  http://digre.pmf.unizg.hr/id/eprint/4148 
Actions (login required)
View Item 