Un algoritmo paralelo para el problema del conjunto independiente

• López Bracho, Rafael ^[1] ; Ortuño Sánchez, María Paula ^[1]
  1. [1] Universidad Autónoma Metropolitana

     Universidad Autónoma Metropolitana

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 7, Nº. 1-2, 2000, págs. 125-134
• Idioma: español
• DOI: 10.15517/rmta.v7i1-2.185
• Enlaces
  • Texto completo (pdf)
• 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.Palabras Clave: Gráfica, Conjunto Independiente, Número de Independencia, Número de Estabilidad, Algoritmo Paralelo.

• Referencias bibliográficas
  • 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,...
  • 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...
  • 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.