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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Publicado: |
2004
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p103_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_Duran |
| Aporte de: |
| id |
paper:paper_15710653_v18_n_p103_Duran |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_15710653_v18_n_p103_Duran2023-06-08T16:24:21Z Clique-independent sets of Helly circular-arc graphs Durán, Guillermo A. Lin, Min Chih Mera, Sergio Fernando 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. 2004 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p103_Duran 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, Guillermo A. Lin, Min Chih Mera, Sergio Fernando 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. |
| author |
Durán, Guillermo A. Lin, Min Chih Mera, Sergio Fernando |
| author_facet |
Durán, Guillermo A. Lin, Min Chih Mera, Sergio Fernando |
| author_sort |
Durán, Guillermo A. |
| 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 |
| publishDate |
2004 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p103_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_Duran |
| work_keys_str_mv |
AT duranguillermoa cliqueindependentsetsofhellycirculararcgraphs AT linminchih cliqueindependentsetsofhellycirculararcgraphs AT merasergiofernando cliqueindependentsetsofhellycirculararcgraphs |
| _version_ |
1768545258203774976 |