Page 12 - Boletín CIMAT Marzo 2021

El objetivo principal de este proyecto, es diseñar algoritmos para encontrar un conjunto independiente fuerte máximo para ciertas clases de gráficas planas que admitan una solución en tiempo polinomial. Es necesario determinar qué propiedades deben tener estas gráficas para que sea posible diseñar algoritmos que en tiempo polinomial encuentren el CIF máximo. Se pretende en primera instancia explorar aquellas gráficas planas que sean muy parecidas a los árboles y a los cactus.
Asimismo, la investigación del Dr. Trejo también pretende diseñar algoritmos de aproximación para el caso de gráficas planas generales. Grosso modo, un algoritmo de aproximación es un algoritmo que en tiempo polinomial encuentra una solución “cercana” al óptimo. Se espera que mientras más cercana se encuentre la solución aproximada a la solución óptima, el algoritmo será más complicado de diseñar.
Además, como objetivos secundarios, se pretende profundizar en el diseño de algoritmos distribuidos para el problema del CIF maximal. Es importante recalcar que el diseño de algoritmos distribuidos representa un reto adicional, debido a que, en
12 Boletín Mensual Investigación de Información
dichos algoritmos, las decisiones se deben tomar considerando únicamente una visión local del sistema.
La ejecución de este proyecto tiene implicaciones positivas en la obtención de resultados académicos de alta calidad, formación de recursos humanos y tiene potenciales aplicaciones que actualmente representan el estudio del conjunto independiente fuerte. Aunado a esto, permite posicionar al sureste de México en el tema de optimización combinatoria.
El proyecto “Diseño de algoritmos para el problema del conjunto independiente fuerte en gráficas planas” está planificado en dos etapas de un año cada una. Durante este tiempo, se pretende dar becas a uno o dos estudiantes de licenciatura que estén interesados en el tema, así como incorportar a un investigador postdoctoral, buscar algunas estancias cortas y asistir a conferencias internacionales.
Así pues, se espera que, a raíz de este proyecto, se fortalezcan las líneas de investigación del Dr. Trejo, no solo con grupos de investigación nacionales, sino que tenga alcance en grupos de investigación internacionales.