03/02/2025
Algoritmos eficientes para problemas de clique máximo y de conjuntos independiente máximo en grafos monopolares y grafos unipolares
Min Chih Lin
Resumen
Se propone en esta tesis, resolver lo más eficientemente posible los problemas de clique máximo y conjunto independiente máximo tanto para la versión sin pesos como para la versión pesada (donde los nodos del grafo tienen pesos asignados) en las siguientes clases de grafos: los grafos monopolares, los grafos unipolares y las clases de grafos relacionadas con las anteriores (conocidas o nuevas a descubrir). Tanto los grafos monopolares como los grafos unipolares son grafos polares que a su vez es una generalización de clases de grafos clásicas de Teoría de Grafos como los grafos bipartitos y grafos split. Hay una diferencia computacionalmente importante entre los grafos monopolares y los grafos unipolares donde el problema del reconocimiento de los primeros es NP-Completo mientras para los segundos existe un algoritmo de tiempo cúbico para reconocerlos. Por ello, sería interesante desarrollar algoritmos robustos que resuelvan los problemas para los grafos monopolares sin saber que si el grafo de entrada es monopolar o no. O bien resuelve el problema en cuestión o bien se da cuenta que el grafo es inválido y en tal caso, ofrecer una evidencia (certificado).
Descripción de la propuesta
—
Conocimientos deseables
Teoría y Algoritmos en grafos
Qué aprenderá el o la estudiante
Aprenderá cómo realizar una investigación orientada a algorítmica en grafos
