A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs

Details A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs

2007-12-20

arxiv.org/abs/0712.3335v1

Computer Science

Data Structures and Algorithms

Scientific paper

We develop a polynomial time 3/2-approximation algorithm to solve the vertex cover problem on a class of graphs satisfying a property called ``active edge hypothesis''. The algorithm also guarantees an optimal solution on specially structured graphs. Further, we give an extended algorithm which guarantees a vertex cover $S_1$ on an arbitrary graph such that $|S_1|\leq {3/2} |S^*|+\xi$ where $S^*$ is an optimal vertex cover and $\xi$ is an error bound identified by the algorithm. We obtained $\xi = 0$ for all the test problems we have considered which include specially constructed instances that were expected to be hard. So far we could not construct a graph that gives $\xi \not= 0$.

Affiliated with

Also associated with

No associations

Rating

A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of 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 A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2612