Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Un algoritmo paralelo para el problema del conjunto independiente
PDF

Palabras clave

Graph
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

López Bracho, R., & Ortuño Sánchez, M. P. (2000). Un algoritmo paralelo para el problema del conjunto independiente. Revista De Matemática: Teoría Y Aplicaciones, 7(1-2), 125–134. https://doi.org/10.15517/rmta.v7i1-2.185

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.


https://doi.org/10.15517/rmta.v7i1-2.185
PDF

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.

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.