Approximability of the Vertex Cover Problem in Power Law Graphs

Details Approximability of the Vertex Cover Problem in Power Law Graphs Approximability of the Vertex Cover Problem in Power Law Graphs

2012-04-04

arxiv.org/abs/1204.0982v2

Computer Science

Data Structures and Algorithms

16 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximability of the Vertex Cover Problem in Power Law Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximability of the Vertex Cover Problem in Power Law Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximability of the Vertex Cover Problem in Power Law Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32501