Treffer: Algorithms for clique-independent sets on subclasses of circular-arc graphs

Title:
Algorithms for clique-independent sets on subclasses of circular-arc graphs
Authors:
DURAN, Guillermo, MIN CHIH LIN, MERA, Sergio, SZWARCFITER, Jayme Luiz
Source:
Traces of the Latin American conference on combinatorics, graphs and applications: a selection of papers from LACGA 2004Discrete applied mathematics. 154(13):1783-1790
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 21 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Clique graphe, Graph clique, Combinatoire, Combinatorics, Combinatoria, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Ensemble indépendant, Independent set, Conjunto independiente, Informatique théorique, Computer theory, Informática teórica, Temps polynomial, Polynomial time, Tiempo polinomial, Cardinalité, Graphe Helly, Helly graph, Graphe arc circulaire, Graphe intersection, Algorithms, Circular-arc graphs, Clique-independent sets, Helly circular-arc graphs
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Departamento de Ingenieria Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Maremática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18032624
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.18032624
Database:
PASCAL Archive

Weitere Informationen

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 3K2-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(n2). These algorithms suppose that an HCA model of the graph is given.