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: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v18_n_p103_Duran |
| Aporte de: |
| Sumario: | 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. |
|---|