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

Ejemplares similares

Ejemplares similares