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).
Palabras clave. grafos monopolares; grafos unipolares; clique máximo; conjunto independiente máximo
Conocimientos deseables. Teoría y Algoritmos en grafos
¿Qué podría aprender quien realice esta tesis? – Aprenderá cómo realizar una investigación orientada a algorítmica en grafos.
Dirección de la tesis
Lin, Min Chih
Departamento de Computación e Instituto de Cálculo
Contacto: oscarlin@dc.uba.ar