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.

[img] PDF
Restricted to Registered users only
Language: Croatian

Download (655kB) | Request a copy
[img] 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)
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 View Item