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

DOI: http://dx.doi.org/10.15439/2025F5317

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 721–726 (2025)

Full text

Abstract. In this paper we describe an exact algorithm that constructs all Pareto optimal solutions of the biobjective minimum risk minimum length spanning trees problem. The method constructs directly the Pareto optimal spanning trees without constructing the entire classes of optimal spanning trees with respect to the length and with respect to the risk criterion. We provide detailed description and mathematical analysis of the proposed algorithms. Also, we illustrate the method using a comprehensive numerical example. The computational complexity of the algorithm that constructs the complete Pareto front of the problem is $O(s(m + n \lg{n}))$, where $s$ is a constant that depends on the number of all Pareto optimal solutions and a predefined constant that can be used to limit the number of constructed solutions.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 4th ed. Cambridge, Massachusetts: MIT Press, 2022, ch. 21, pp. 585–603. ISBN 0-262-04630-X
2. R. C. Prim, “Shortest connection networks and some generalizations,” The Bell System Technical Journal, vol. 36, no. 6, pp. 1389–1401, 1957. https://dx.doi.org/10.1002/j.1538-7305.1957.tb01515.x
3. 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. https://dx.doi.org/10.1145/28869.28874
4. R. M. Ramos, S. Alonso, J. Sicilia, and C. González, “The problem of the optimal biobjective spanning tree,” European Journal of Operational Research, vol. 111, no. 3, pp. 617–628, 1998. https://dx.doi.org/10.1016/S0022-0000(05)80064-9
5. D. Rocha, E. Goldbarg, and M. Goldbarg, “A memetic algorithm for the biobjective minimum spanning tree problem,” in Evolutionary Computation in Combinatorial Optimization, J. Gottlieb and G. R. Raidl, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. https://dx.doi.org/10.1007/11730095_19. ISBN 978-3-540-33179-7 pp. 222–233.
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. https://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. https://dx.doi.org/10.1007/s10898-013-0124-4
8. H. W. Corley, “Efficient spanning trees,” Journal of Optimization Theory and Applications, vol. 45, pp. 481–485, 1985. https://dx.doi.org/10.1007/BF00938448
9. S. Fidanova and M. Ganzha, “Ant colony optimization for workforce planning with hybridization,” in Proceedings of the 18th Conference on Computer Science and Intelligence Systems, ser. Annals of Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, and D. Śl˛ezak, Eds., vol. 35. IEEE, 2023. https://dx.doi.org/10.15439/2023F9586 p. 955–959.
10. L. M. Laskov and M. L. Marinov, “Pareto optimal solutions of the biobjective minimum length minimum risk spanning trees problem,” in Proceedings of the of the 19th Conference on Computer Science and Intelligence Systems, ser. ACSIS, M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, and D. Śl˛ezak, Eds., vol. 39. IEEE, 2024. https://doi.org/10.15439/2024F2913. ISSN 300-5963 pp. 405–416.