Logo PTI Logo FedCSIS

Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 39

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

,

DOI: http://dx.doi.org/10.15439/2024F2913

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 405–416 ()

Full text

Abstract. 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.

References

  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