Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V
85327

05.04.2012

Approximability of the Vertex Cover Problem in Power Law Graphs
Mikael Gast, Mathias Hauptmann
[Download PostScript] [Download PDF]

In this paper we construct an approximation algorithm for the Minimum Vertex Cover Problem (Min-VC) with an expected approximation ratio of 2-f(beta) for random Power Law Graphs (PLG) in the (alpha,beta)-model of Aiello et. al., where f(beta) is a strictly positive function of the parameter beta. We obtain this result by combining the Nemhauser and Trotter approach for Min-VC with a new deterministic rounding procedure which achieves an approximation ratio of 3/2 on a subset of low degree vertices for which the expected contribution to the cost of the associated linear program is sufficiently large.

Last Change: 11/05/14 at 11:00:36
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope