Grafos, algoritmos y optimización

En esta línea de investigación se estudian diferentes clases de grafos y se analizan algunos de los problemas clásicos de teoría de grafos (conjunto independiente máximo, clique máxmo, coloreo de vértices o aristas de un grafo, recubrimiento mínimo), restringidos a esas clases. Uno de los objetivos es, dado un problema y una clase de grafos, averiguar la situación de ese problema en términos de complejidad computacional, para la clase en cuestión. O bien intentamos probar que el problema es intratable computacionalmente (NP-Hard) para la clase, o bien hallamos algoritmos polinomiales que resuelven el problema para cualquier grafo perteneciente a la clase. Se estudian también caracterizaciones estructurales de diferentes clases de grafos y se buscan caracterizaciones parciales o totales de las mismas, por medio de estructuras prohibidas. Existen muchos problemas abiertos de este tipo en clases de grafos bien estudiadas, para las cuales no se conocen este tipo de caracterizaciones. En lo que hace a temas de Optimización, trabajamos en el desarrollo de algoritmos con base en métodos exactos de Programación Lineal Entera, así como también en la implementación de métodos heurísticos para resolución de problemas reales.  Muchos de los problemas aquí mencionados están motivados por problemas reales de la Investigación Operativa (IO), y en ese sentido, existe una ligazón importante entre esta línea de trabajo y la línea de transferencia del Instituto vinculada a la IO.