Approximation algorithms for clique transversals on some graph classes

Given a graph 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, li...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Vasiliev, S.
Formato: JOUR
Materias:
Approximation algorithms
Clique transversal
Graph classes
NP-hard
Algorithms
Distributed computer systems
Graph theory
Graphic methods
Adjacent vertices
Bounded degree graphs
Cardinalities
Graph class
Non negatives
Planar graph
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00200190_v115_n9_p667_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario:Given a graph 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 ⌉(-approximation for bounded degree graphs and a 3-approximation for planar graphs. © 2015 Elsevier B.V.

Ejemplares similares