Un algoritmo paralelo para el problema del conjunto independiente

Fecha

2009-02-19 00:00:00

Tipo

artículo original

Autores

López Bracho, Rafael
Ortuño Sánchez, María Paula

Título de la revista

ISSN de la revista

Título del volumen

Editor

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.

Descripción

Palabras clave