El problema del máximo conjunto independiente en un grafo.

Mairal Buera, Claudia
García Olaverri, Alfredo (dir.)

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

Graduado en Matemáticas

Resumen: En teoría de grafos, un conjunto independiente es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. El propósito principal de este Trabajo Fin de Grado reside en el estudio del problema de hallar un conjunto independiente máximo en un grafo y en su complejidad computacional. Este problema es equivalente a otros problemas básicos de grafos (como el de hallar un máximo clique o recubrimiento de vértices mínimo), y es un problema de la clase NP-Hard que aparece de forma natural en muchas aplicaciones reales.
El trabajo incluye las siguientes partes:
- Una descripción del problema, problemas de grafos equivalentes y relacionados. Aplicaciones.
- Complejidad del problema: introducción a la complejidad computacional y demostración de que el problema es NP-Hard.
- Algoritmos exactos y algoritmos heurísticos para hallar un conjunto independiente óptimo. Formulación del problema como un PLE. El problema del máximo conjunto independiente en grafos de intervalo y los problemas de Scheduling.

Tipo de Trabajo Académico: Trabajo Fin de Grado