Back to search

Universidad de la Laguna

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

Abstract

dc:description.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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pérez Brito, Dionisio
Advisor dc:contributor.advisor
  • Moreno Pérez, José Antonio

Rights

dc:rights.accessrights
Statement dc:rights.accessrights
  • info:eu-repo/semantics/openAccess
  • Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Language dc:language.iso
es

Identifiers

dc:identifier.*
Repository record dc:identifier.uri
http://riull.ull.es/xmlui/handle/915/21104

Chain of custody

source
Harvested from
Universidad de la Laguna
Base URL
riull.ull.es/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Pérez Brito, Dionisio. Arboles y herísticas en localización: El modelo Centdian múltiple. 1998. http://riull.ull.es/xmlui/handle/915/21104