Clique-independent sets of Helly circular-arc graphs

A circular-arc graph is the intersection graph of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L.
Formato:	JOUR
Materias:	algorithms circular-arc graphs clique-independent sets Helly circular-arc graphs
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_Duran
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_15710653_v18_n_p103_Duran
record_format	dspace
spelling	todo:paper_15710653_v18_n_p103_Duran2023-10-03T16:26:59Z Clique-independent sets of Helly circular-arc graphs Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L. algorithms circular-arc graphs clique-independent sets Helly circular-arc graphs A circular-arc graph is the intersection graph of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose algorithms for finding the maximum cardinality and weight of a clique-independent set of a over(3 K2, -)-free CA graph. Also, we apply the algorithms to the special case of an H C A graph. The complexity of the proposed algorithm for the cardinality problem in H C A graphs is O(n). This represents an improvement over the existing algorithm, whose complexity is O (n2). © 2005 Elsevier B.V. All rights reserved. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Mera, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_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	algorithms circular-arc graphs clique-independent sets Helly circular-arc graphs
spellingShingle	algorithms circular-arc graphs clique-independent sets Helly circular-arc graphs Durán, G. Lin, M.C. Mera, S. Szwarcfiter, J.L. Clique-independent sets of Helly circular-arc graphs
topic_facet	algorithms circular-arc graphs clique-independent sets Helly circular-arc graphs
description	A circular-arc graph is the intersection graph of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose algorithms for finding the maximum cardinality and weight of a clique-independent set of a over(3 K2, -)-free CA graph. Also, we apply the algorithms to the special case of an H C A graph. The complexity of the proposed algorithm for the cardinality problem in H C A graphs is O(n). This represents an improvement over the existing algorithm, whose complexity is O (n2). © 2005 Elsevier B.V. All rights reserved.
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	Clique-independent sets of Helly circular-arc graphs
title_short	Clique-independent sets of Helly circular-arc graphs
title_full	Clique-independent sets of Helly circular-arc graphs
title_fullStr	Clique-independent sets of Helly circular-arc graphs
title_full_unstemmed	Clique-independent sets of Helly circular-arc graphs
title_sort	clique-independent sets of helly circular-arc graphs
url	http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_Duran
work_keys_str_mv	AT durang cliqueindependentsetsofhellycirculararcgraphs AT linmc cliqueindependentsetsofhellycirculararcgraphs AT meras cliqueindependentsetsofhellycirculararcgraphs AT szwarcfiterjl cliqueindependentsetsofhellycirculararcgraphs
_version_	1807322421124923392

Clique-independent sets of Helly circular-arc graphs

Ejemplares similares