Pareto Optimal Solutions of the Biobjective Minimum Length Minimum Risk Spanning Trees Problem

• Autorzy: Laskov Lasko , Marinov Marin

Identyfikatory

DOI

10.15439/2024F2913

• Konferencja: Federated Conference on Computer Science and Information Systems (19 ; 08-11.09.2024 ; Belgrade, Serbia)
• Języki publikacji: EN

Abstrakty

EN

We propose an exact method that finds the complete Pareto front of the biobjective minimum length minimum risk spanning trees problem. The proposed method is based on the solution of two subproblems. The first subproblem is to find a list of all minimum spanning trees with respect of the length criterion. The second subproblem is to compose the complete Pareto front itself, based on the list of all Pareto optimal trees with minimal length. We provide detailed mathematical proofs for the correctness and running time complexity of all proposed algorithms. We also illustrate all algorithms with detailed numerical examples.

Słowa kluczowe

EN

computer science; Pareto optimization; computational complexity

PL

informatyka; optymalizacja Pareto; złożoność obliczeniowa

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2024
• Tom: Vol. 39
• Strony: 405--416
• Opis fizyczny: Bibliogr. 11 poz., tab., wz.

Twórcy

autor

Laskov Lasko

• Informatics Department New Bulgarian University 21 Montevideo Str., 1618 Sofia, Bulgaria

• https://orcid.org/0000-0003-1833-8184

autor

Marinov Marin

• Informatics Department New Bulgarian University 21 Montevideo Str., 1618 Sofia, Bulgaria

• https://orcid.org/0009-0003-9544-819X

Bibliografia

• 1. J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical society, vol. 7, no. 1, pp. 48–50, 1956.
• 2. R. C. Prim, “Shortest connection networks and some generalizations,” The Bell System Technical Journal, vol. 36, no. 6, pp. 1389–1401, 1957. http://dx.doi.org/10.1002/j.1538-7305.1957.tb01515.x
• 3. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959. http://dx.doi.org/10.1007/bf01386390
• 4. C. F. Bazlamaçcı and K. S. Hindi, “Minimum-weight spanning tree algorithms a survey and empirical study,” Computers & Operations Research, vol. 28, no. 8, pp. 767–785, 2001. http://dx.doi.org/10.1016/S0305-0548(00)00007-1
• 5. P. C. Pop, “The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances,” European Journal of Operational Research, vol. 283, no. 1, pp. 1–15, 2020. http://dx.doi.org/10.1016/j.ejor.2019.05.017
• 6. S. Steiner and T. Radzik, “Computing all efficient solutions of the biobjective minimum spanning tree problem,” Computers & Operations Research, vol. 35, no. 1, pp. 198–211, 2008. http://dx.doi.org/10.1016/j.cor.2006.02.023
• 7. A. C. Santos, D. R. Lima, and D. J. Aloise, “Modeling and solving the bi-objective minimum diameter-cost spanning tree problem,” Journal of Global Optimization, vol. 60, pp. 195–216, 2014. http://dx.doi.org/10.1007/s10898-013-0124-4
• 8. de Sousa, Ernando Gomes, Santos, Andréa Cynthia, and Aloise, Dario José, “An exact method for solving the bi-objective minimum diametercost spanning tree problem,” RAIRO-Oper. Res., vol. 49, no. 1, pp. 143–160, 2014. http://dx.doi.org/10.1051/ro/2014029
• 9. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 3rd ed. Cambridge, Massachusetts: The MIT Press, 2009. http://dx.doi.org/10.5555/1614191
• 10. M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” Journal of the ACM, vol. 34, no. 3, pp. 596–615, July 1987. http://dx.doi.org/10.1145/28869.28874
• 11. B. Korte and J. Vygen, Spanning Trees and Arborescences. Berlin,Heidelberg: Springer Berlin Heidelberg, 2018, pp. 133–157. ISBN 978-3-662-56039-6

Uwagi

Thematic Sessions: Regular Papers