Algorithms for finding clique-transversals of graphs

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. It is NP-hard to determine the minimum cardinality τ c of a clique-transversal of G. In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial t...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L.
Formato: JOUR
Materias:
3K2̄-free circular-arc graphs
Algorithms
Circular-arc graphs
Clique-transversals
Helly circular-arc graphs
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_02545330_v157_n1_p37_Duran
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares