Arboles y herísticas en localización: El modelo Centdian múltiple

Abstract

Con el objetivo de reflejar el estado actual de los problemas de localización en árboles, se realiza un repaso de los modelos clásicos tanto en el árbol como en su representación más simple, la recta real. Además, se recuerdan otros problemas que también tienen gran relevancia en el ámbito de la localización en árboles. En esta línea, se proponen varias estrategias heurísticas para resolver problemas de localización en grafos, haciendo uso de los algoritmos construidos para árboles, obteniéndose en muy poco tiempo soluciones próximas a la óptima. También hay que resaltar los resultados de la heurística VNDS, que ha sido diseñada para resolver problemas de optimización combinatoria en grafos de dimensiones considerables. Esta ha sido probada con grafos del orden de 6000 vértices, mejorando apreciablemente los resultados obtenidos con otras heurísticas. En la segunda, se estudia la función Centdian en un grafo considerando la función Centro ponderada, generalizando así el modelo de Halpern. Se realiza un análisis del 2-lamda-Centdian, y se propone un algoritmo de complejidad O(m2n4), donde m y n son respectivamente el número de aristas y vértices del grafo considerado. Además se presenta un contraejemplo al conjunto finito dominante propuesto por Hooker y otros. En contrapartida se presenta un nuevo conjunto finito dominante para el problema p-lamda-Centdian en un grafo con una demostración detallada del mismo. Finalmente, como consecuencia de éste, se propone un algoritmo exacto. El trabajo concluye estudiando el problema p-lamda-Centdian en un árbol, proponiendose el primer algoritmo polinomial para el problema p-lamda-Centdian (generalizado o no) en árboles