EL PROBLEMA MODIFICADO DE UN CENTRO EN ÁRBOLES: VARIACIONES Y APLICACIONES
DOI:
https://doi.org/10.56238/revgeov17n5-143Palabras clave:
Problemas de Localización, Problema del Centro Único, Problemas MinimaxResumen
Se presenta una variación asimétrica del problema del centro único en árboles y un método para su solución en tiempo O(n). El método emplea una reducción en tiempo lineal del problema, basada en una técnica que utiliza vértices simulados. Según los resultados computacionales obtenidos, el método presentado mostró un mejor rendimiento en comparación con los métodos clásicos para resolver el problema del centro único en árboles.
Descargas
Referencias
Burkard, R.; Krarup, J. A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing 60(3), 193–216. 1998.
Çalık, H.; Labbé, M.; Yaman, H. p-center problems. Location Science, 79–92. 2015.
Daskin, M.S.; Maass, K.L. “The p-Median Problem”. In: Laporte, G., Nickel, S., Saldanha da Gama, F. (eds.) Location Science, pp. 21–45. Springer. 2015.
Dearing, P.M.; Francis, R.L. A minimax location problem on a network. Transportation Science 8(4), 333–343. 1974.
Goldman, A.J. Optimal center location in simple networks. Transportation Science 5(2), 212–221. 1971.
Gortz, I.L.; Wirth, A. Asymmetry in k-center variants. Theoretical Computer Science 361(2), 188–199. 2006.
Hakimi, S.L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3), 450–459. 1964.
Hakimi, S.L. Optimum distribution of switching centers in a communication network and some related graph-theoretic problems. Operations Research 13(3), 462–475. 1965.
Hakimi, S.L.; Schmeichel, E.F.; Pierce, J.G. On p-centers in networks. Transportation Science 12(1), 1–15. 1978.
Hua, L.-K. et al. Application of mathematical methods to wheat harvesting. Chinese Mathematics 2(7791), 8. 1962.
Kariv, O.; Hakimi, S.L. An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics 37(3), 513–538. 1979.
Kariv, O.; Hakimi, S.L. An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics 37(3), 539–560. 1979.
Liu, Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research 111(1), 1–20. 2019.
Megiddo, N. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12(4), 759–776. 1983.
Nguyen, K.T.; Nguyen-Thu, H.; Hung, N.T. Combinatorial algorithms for the uniformcost inverse 1-center problem on weighted trees. Acta Math. Vietnam 44(3), 813–831. 2019.
Tamir, A. An O(pn2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters 19(2), 59–64. 1996.
Tansel, B.; Francis, R.L.; Lowe, T.J. Location on networks: A survey. Part I: The p-center and p-median problems. Management Science 29(2), 482–497. 1983.
Wang, H.; Zhang, J. An O(n log n)-time algorithm for the k-center problem in trees. SIAM J. Comput. 50(2), 602–635. 2021.
