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.
Licencia
Copyright
© Revista de Matemática: Teoría y Aplicaciones, 2000
Afiliaciones
Rafael López Bracho
Universidad Autónoma Metropolitana-Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, 02200 México, D.F. México
María Paula Ortuño Sánchez
Universidad Autónoma Metropolitana-Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, 02200 México, D.F. México
Cómo citar
Comentarios
Un algoritmo paralelo para el problema del conjunto independiente
Vol. 7 Núm. 1-2 (2000): Revista de Matemática: Teoría y Aplicaciones
Publicado: Feb 1, 2000
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.