Grupo de investigación:- SAFE, MARTÍN (Director)
- CAPPA, JUAN ANGEL
- SABATINI, GERMÁN NICOLÁS
- SUÁREZ ALBANESI, ROCÍO BELÉN
- VERGARA, MARTINA
Resumen:Los objetivos principales de este proyecto son encontrar caracterizaciones estructurales de ciertas clases de grafos y explotar dichas caracterizaciones para el desarrollo de algoritmos eficientes. Una caracterización estructural de una clase de grafos permite, en muchos casos, diseñar algoritmos eficientes para el problema de reconocimiento de la clase y, a su vez, es esencial para el diseño de algoritmos de reconocimiento con certificado negativo, es decir, algoritmos que, cuando el grafo de entrada no pertenece a la clase correspondiente, devuelven evidencia que permite corroborar ese hecho de forma independiente y simple. En este proyecto proponemos estudiar estructural y algorítmicamente subclases y variantes de los grafos perfectos y algunas clases de grafos de intersección (grafos arco-circulares y grafos círculo). Para los grafos perfectos, ciertos problemas clásicos de optimización que son considerados intratables para la clase general de grafos (como coloreo, clique máxima, conjunto independiente máximo, etc.) pueden resolverse en tiempo polinomial mediante el método del elipsoide. Otro conjunto de problemas considerados igualmente intratables para la clase general de grafos, se saben resolver eficientemente para los grafos arco-circulares (por ejemplo, cubrimiento por cliques, conjunto independiente máximo, dominación, etc.) o los grafos círculo (por ejemplo, 3-coloreo, clique máxima, conjunto independiente máximo, etc.). Estos hechos son una fuente de interés para estudiar estas clases de grafos (y sus subclases). En efecto, estas clases de grafos han recibido un gran interés en la literatura especializada en los últimos años.