Palabras clave
Independent Set
Independence Number
Stability Number
Parallel Algorithm
Gráfica
Conjunto Independiente
Número de Independencia
Número de Estabilidad
Algoritmo Paralelo
Cómo citar
Resumen
Un conjunto S de vértices de una gráfica G es independiente si no existen dos vértices de S que sean adyacentes, esto es, la subgráfica de G inducida por S no tiene aristas. En este trabajo presentaremos un algoritmo paralelo que permite la obtención de todos los conjuntos independientes maximales de una gráfica. Presentaremos los fundamentos del algoritmo y algunas propiedades derivadas de éstos.
Citas
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.