Construcción de Poliominos Extremos vía Programación Dinámica

Ponente(s): Manuel Montes Y Morales, Hugo Adán Cruz Suárez, Saylé Sigarreta Ricardo

Un índice topológico es una función que asigna valores a una estructura molecular, reflejando propiedades como la reactividad, la actividad biológica, entre otras. En esta plática estamos interesados en índices que estén basados en los grados de los vértices asociados a lo que se conocen como grafos moleculares, siendo las cadenas de poliominos un caso particular. El objetivo principal de nuestra investigación es abordar el problema de identificar y caracterizar poliominos extremos, es decir, aquellos que alcanzan el valor máximo o mínimo bajo un índice topológico dado. En el trabajo logramos a partir de programación dinámica proveer un algoritmo que construye en tiempo lineal un poliomino extremo (máximo o mínimo), bajo cualquier índice y de cualquier tamaño deseado. Además, se halló una nueva construcción, la cual logra determinar no sólo un poliomino extremo, sino todos para el índice en cuestión. Esta construcción permite contarlos en tiempo lineal y generarlos explícitamente, en el peor de los casos, en tiempo exponencial. Como resultado adicional, a partir de la construcción teórica se lograron caracterizar los poliominos extremos para el índice aumentado de Zagreb, resolviendo así un problema abierto en teoría de grafos.