Un algoritmo paralelo para el problema del conjunto independiente

Un algoritmo paralelo para el problema del conjunto independiente

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 d...

Descripción completa

Detalles Bibliográficos
Autores principales: López Bracho, Rafael, Ortuño Sánchez, María Paula
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2000
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/185
id RMTA185
record_format ojs
spelling RMTA1852022-01-17T17:16:18Z Un algoritmo paralelo para el problema del conjunto independiente López Bracho, Rafael Ortuño Sánchez, María Paula Graph Independent Set Independence Number Stability Number Parallel Algorithm Gráfica Conjunto Independiente Número de Independencia Número de Estabilidad Algoritmo Paralelo 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2000-02-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/185 10.15517/rmta.v7i1-2.185 Revista de Matemática: Teoría y Aplicaciones; Vol. 7 No. 1-2 (2000): Revista de Matemática: Teoría y Aplicaciones; 125-134 Revista de Matemática: Teoría y Aplicaciones; Vol. 7 Núm. 1-2 (2000): Revista de Matemática: Teoría y Aplicaciones; 125-134 Revista de Matemática; Vol. 7 N.º 1-2 (2000): Revista de Matemática: Teoría y Aplicaciones; 125-134 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/185/165 Derechos de autor 2000 Revista de Matemática: Teoría y Aplicaciones
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language spa
format Online
author López Bracho, Rafael
Ortuño Sánchez, María Paula
spellingShingle López Bracho, Rafael
Ortuño Sánchez, María Paula
Un algoritmo paralelo para el problema del conjunto independiente
author_facet López Bracho, Rafael
Ortuño Sánchez, María Paula
author_sort López Bracho, Rafael
description 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.
title Un algoritmo paralelo para el problema del conjunto independiente
title_short Un algoritmo paralelo para el problema del conjunto independiente
title_full Un algoritmo paralelo para el problema del conjunto independiente
title_fullStr Un algoritmo paralelo para el problema del conjunto independiente
title_full_unstemmed Un algoritmo paralelo para el problema del conjunto independiente
title_sort un algoritmo paralelo para el problema del conjunto independiente
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2000
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/185
work_keys_str_mv AT lopezbrachorafael unalgoritmoparaleloparaelproblemadelconjuntoindependiente
AT ortunosanchezmariapaula unalgoritmoparaleloparaelproblemadelconjuntoindependiente
_version_ 1811744057576128512

Ejemplares similares