Copyright
© Revista de Matemática: Teoría y Aplicaciones, 2014
Afiliaciones
Rafael López Bracho
Universidad Autónoma Metropolitana Azcapotzalco, Departamento de Sistemas
María Paula Ortuño Sánchez
Universidad Autónoma Metropolitana Azcapotzalco, Departamento de Sistemas
Cómo citar
López BrachoR., & Ortuño SánchezM. (2009). 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
Comentarios
Un algoritmo paralelo para el problema del conjunto independiente
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.
Palabras Clave: Gráfica, Conjunto Independiente, Número de Independencia, Número de Estabilidad, Algoritmo Paralelo.