Algorithms for clique-independent sets on subclasses of circular-arc graphs
Author | dc.contributor.author | Durán Maggiolo, Guillermo | |
Author | dc.contributor.author | Lin, Min Chih | es_CL |
Author | dc.contributor.author | Mera, Sergio | es_CL |
Author | dc.contributor.author | Szwarcfiter, Jayme Luiz | es_CL |
Admission date | dc.date.accessioned | 2009-03-30T18:07:23Z | |
Available date | dc.date.available | 2009-03-30T18:07:23Z | |
Publication date | dc.date.issued | 2006-08-15 | |
Cita de ítem | dc.identifier.citation | DISCRETE APPLIED MATHEMATICS Volume: 154 Issue: 13 Pages: 1783-1790 Published: AUG 15 2006 | en |
Identifier | dc.identifier.issn | 0166-218X | |
Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/124838 | |
Abstract | dc.description.abstract | A circular-arc graph is the intersection graph of arcs on 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 polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K(2)-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n(2)). These algorithms suppose that an HCA model of the graph is given. | en |
Lenguage | dc.language.iso | en | en |
Publisher | dc.publisher | ELSEVIER | en |
Keywords | dc.subject | BALANCED GRAPHS | en |
Título | dc.title | Algorithms for clique-independent sets on subclasses of circular-arc graphs | en |
Document type | dc.type | Artículo de revista |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas