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

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

Item Type: Thesis (Diploma thesis) Nogo, Goranka 2015 33 NATURAL SCIENCES > Mathematics Faculty of Science > Department of Mathematics Iva Prah 20 Oct 2015 10:29 20 Oct 2015 10:29 http://digre.pmf.unizg.hr/id/eprint/4148