Conjunto dominante conexo de un grafo.

Díez Corral, Javier
García Olaverri, Alfredo (dir.)

Universidad de Zaragoza, CIEN, 2020
Departamento de Métodos Estadísticos,

Graduado en Matemáticas

Resumen: El objetivo de este trabajo es el estudio del problema del cálculo de un conjunto dominante conexo de cardinal de tamaño mínimo en un grafo no dirigido. La principal aplicación de este problema se halla en la optimización del rendimiento de redes de comunicaciones. El tema central del trabajo estará dedicado a la demostración de que el problema pertenece a la clase de complejidad computacional NP-Completo así como a la descripción y análisis de tres algoritmos que permiten obtener una solución aproximada al problema en tiempo polinómico. Se incluye también un breve estudio del problema en triangulaciones planas y casi-triangulaciones.

Tipo de Trabajo Académico: Trabajo Fin de Grado