A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs
| dc.creator | Han, Qiaoming | |
| dc.creator | Punnen, Abraham P. | |
| dc.creator | Ye, Yinyu | |
| dc.date | 2007-12-20 | |
| dc.date.accessioned | 2026-07-07T08:50:32Z | |
| dc.date.available | 2026-07-07T08:50:32Z | |
| dc.description | 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^*|+ξ$ where $S^*$ is an optimal vertex cover and $ξ$ is an error bound identified by the algorithm. We obtained $ξ= 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 $ξ\not= 0$. | |
| dc.identifier | https://arxiv.org/abs/0712.3335 | |
| dc.identifier | http://arxiv.org/abs/0712.3335 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/144631 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2; G.2.2; G.1.6 | |
| dc.title | A polynomial time $\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs | |
| dc.type | text |