Approximation algorithms for clique transversals on some graph classes
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.
approximation algorithms clique transversal graph classes np-hard