1. Un algoritmo paralelo para el problema del conjunto independiente
- Author
-
Rafael López Bracho and María Paula Ortuño Sánchez
- Subjects
Stability Number ,Materials Science (miscellaneous) ,lcsh:Mathematics ,Independent Set ,Gráfica ,Número de Independencia ,Algoritmo Paralelo ,lcsh:QA1-939 ,Graph ,Industrial and Manufacturing Engineering ,Número de Estabilidad ,Conjunto Independiente ,Business and International Management ,Independence Number ,Parallel Algorithm - Abstract
A set S of vertices in a graph G is independent if there does not exist two adjacent vertices in S, that is, the subgraph of G induced by S does not have edges. In this work we present a parallel algorithm that permits to obtain all maximal independent sets in a graph. We present the foundations of the algorithm and some properties. 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.
- Published
- 2009