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

Full description

Bibliographic Details
Main Authors:	López Bracho, Rafael, Ortuño Sánchez, María Paula
Format:	Online
Language:	spa
Published:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2000
Online Access:	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

Un algoritmo paralelo para el problema del conjunto independiente

Similar Items