Open AccessUn algoritmo paralelo para el problema del conjunto independiente
Author(s) -
Rafael Bracho,
María Paula Ortuño Sánchez
Publication year - 2000
Publication title -
revista de matemáticas
Language(s) - Spanish
Resource type - Journals
eISSN - 2215-3373
pISSN - 1409-2433
DOI - 10.15517/rmta.v7i1-2.185
Subject(s) - humanities , physics , philosophy , mathematics
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.