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

id	todo:paper_02545330_v157_n1_p37_Duran
record_format	dspace
spelling	todo:paper_02545330_v157_n1_p37_Duran2023-10-03T15:11:33Z Algorithms for finding clique-transversals of graphs Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L. 3K2̄-free circular-arc graphs Algorithms Circular-arc graphs Clique-transversals Helly circular-arc 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 time, for fixed τ c . This algorithm is employed for finding the minimum cardinality clique-transversal of 3K2̄-free circular-arc graphs in O(n 4) time. Further we describe an algorithm for determining τ c of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n 2) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in O(n 2) time. © 2007 Springer Science+Business Media, LLC. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_02545330_v157_n1_p37_Duran
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	3K2̄-free circular-arc graphs Algorithms Circular-arc graphs Clique-transversals Helly circular-arc graphs
spellingShingle	3K2̄-free circular-arc graphs Algorithms Circular-arc graphs Clique-transversals Helly circular-arc graphs Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L. Algorithms for finding clique-transversals of graphs
topic_facet	3K2̄-free circular-arc graphs Algorithms Circular-arc graphs Clique-transversals Helly circular-arc graphs
description	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 time, for fixed τ c . This algorithm is employed for finding the minimum cardinality clique-transversal of 3K2̄-free circular-arc graphs in O(n 4) time. Further we describe an algorithm for determining τ c of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n 2) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in O(n 2) time. © 2007 Springer Science+Business Media, LLC.
format	JOUR
author	Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L.
author_facet	Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L.
author_sort	Durán, G.
title	Algorithms for finding clique-transversals of graphs
title_short	Algorithms for finding clique-transversals of graphs
title_full	Algorithms for finding clique-transversals of graphs
title_fullStr	Algorithms for finding clique-transversals of graphs
title_full_unstemmed	Algorithms for finding clique-transversals of graphs
title_sort	algorithms for finding clique-transversals of graphs
url	http://hdl.handle.net/20.500.12110/paper_02545330_v157_n1_p37_Duran
work_keys_str_mv	AT durang algorithmsforfindingcliquetransversalsofgraphs AT linmc algorithmsforfindingcliquetransversalsofgraphs AT meras algorithmsforfindingcliquetransversalsofgraphs AT szwarcfiterjl algorithmsforfindingcliquetransversalsofgraphs
_version_	1807323765940420608

Algorithms for finding clique-transversals of graphs

Ejemplares similares