Keywords
Independent Set
Independence Number
Stability Number
Parallel Algorithm
Gráfica
Conjunto Independiente
Número de Independencia
Número de Estabilidad
Algoritmo Paralelo
How to Cite
Abstract
A set S of vertices in a graph G is independent if there does not exist two adjacent vertices in S, that is, the subgraph of G induced by S does not have edges. In this work we present a parallel algorithm that permits to obtain all maximal independent sets in a graph. We present the foundations of the algorithm and some properties.
References
Berge, C. (1970) Graphes et Hypergraphes. Dunod, Paris.
Christofides, N. (1975) Graph Theory: An Algorithmic Approach. Academic Press, New York.
Füredi, Z. (1987) “The ‘number of maximal independent sets in connected graphs”, Journal of Graph Theory 11(4): 463–470.
Garey, M. R.; Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. Publishers, San Francisco.
Golumbic, M. C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
Griggs, J. R.; Grinstead, C. M.; Guichard, D.R. (1988) “The number of maximal independent sets in a connected graph”, Discrete Mathematics 68: 211–220.
Gutiérrez, M. A. (1991) La Técnica de Recocido Simulado. Tesis doctoral, UNAM, México.
Harary, F. (1972) Graph Theory. Addison Wesley, Reading MS.
Neumann-Lara, V. (1985) “Introducción a la teoría de gráficas”, IV Coloquio del Departamento de Matemáticas, CINVESTAV, México.
Papadimitriou, C. H.; Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs N.J.
Syslo, M.; Deo, N.; Kowalik, J. (1983) Discrete Optimization Algorithms with Pascal Programs. Prentice Hall Inc., Englewood Cliffs N.J.