| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427104 | Information Processing Letters | 2015 | 4 Pages |
•A 3-approximation algorithm for unweighted line graphs.•A 4-approximation algorithm for weighted line graphs.•A 3-approximation algorithm for planar graphs.•A ⌈(Δ(G)+1)/2⌉⌈(Δ(G)+1)/2⌉-approximation algorithm for bounded degree graphs.
Given a graph G=(V,E)G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G . Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2⌉⌈(Δ(G)+1)/2⌉-approximation for bounded degree graphs and a 3-approximation for planar graphs.
