El problema de la ruta impar más corta de peso mínimo en gráficas conservativas

Ponente(s): Lydia Mirabel Mendoza Cadena, Alpár Jüttner, Csaba Király, Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi

Consideramos el problema de la RUTA IMPAR MÁS CORTA, en el cual, dada una gráfica no dirigida G=(V,E), una función de peso w : E → R, y dos vérties s y t, el objetivo es encontrar una ruta de s a t de longitud impar y de peso mínimo. Recientemente, Schlotter y Sebő demostraron que este problema es NP-completo, incluso si la función de peso es conservativa, es decir, no hay ciclos de peso negativo. En esta plática, mostramos un algoritmo combinatorio que corre en tiempo polinomial cuando la función de peso es conservativa y las aristas que tienen peso negativo forman un árbol. También consideramos la variante de este problema en donde buscamos una ruta de s a t de longitud impar que alterna entre dos conjuntos, llamada RUTA IMPAR DE PARIDAD RESTRINGIDA.