{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:31:02Z","timestamp":1777714262251,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T00:00:00Z","timestamp":1611532800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T00:00:00Z","timestamp":1611532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["SFRH\/BD\/91647\/2012"],"award-info":[{"award-number":["SFRH\/BD\/91647\/2012"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Programa Operacional Capital Humano","award":["SFRH\/BSAB\/139892\/2018"],"award-info":[{"award-number":["SFRH\/BSAB\/139892\/2018"]}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["PTDC\/CCI-COM\/31198\/2017"],"award-info":[{"award-number":["PTDC\/CCI-COM\/31198\/2017"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article introduces a new algorithm for computing the set of supported non-dominated points in the objective space and all the corresponding efficient solutions in the decision space for the multi-objective spanning tree (MOST) problem. This algorithm is based on the connectedness property of the set of efficient supported solutions and uses a decomposition of the weight set in the weighting space defined for a parametric version of the MOST problem. This decomposition is performed through a space reduction approach until an indifference region for each supported non-dominated point is obtained. An adjacency relation defined in the decision space is used to compute all the supported efficient spanning trees associated to the same non-dominated supported point as well as to define the indifference region of the next points. An in-depth computational analysis of this approach for different types of networks with three objectives is also presented.<\/jats:p>","DOI":"10.1007\/s10589-020-00251-6","type":"journal-article","created":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T08:05:19Z","timestamp":1611561919000},"page":"491-528","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Finding multi-objective supported efficient spanning trees"],"prefix":"10.1007","volume":"78","author":[{"given":"Pedro","family":"Correia","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7525-8901","authenticated-orcid":false,"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 Rui","family":"Figueira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,25]]},"reference":[{"key":"251_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01459088","volume":"99","author":"W Ackermann","year":"1928","unstructured":"Ackermann, W.: Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann. 99, 118\u2013133 (1928)","journal-title":"Math. Ann."},{"key":"251_CR2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River (1993)"},{"issue":"1","key":"251_CR3","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.ejor.2015.06.072","volume":"248","author":"MJ Alves","year":"2016","unstructured":"Alves, M.J., Costa, J.P.: Graphical exploration of the weight space in three-objective mixed integer linear programs. Eur. J. Oper. Res. 248(1), 72\u201383 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"12","key":"251_CR4","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/S0305-0548(96)00026-3","volume":"23","author":"KA Andersen","year":"1996","unstructured":"Andersen, K.A., J\u00f6rnsten, K., Lind, M.: On bicriterion minimal spanning trees: an approximation. Comput. Oper. Res. 23(12), 1171\u20131182 (1996)","journal-title":"Comput. Oper. Res."},{"key":"251_CR5","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-662-48350-3_25","volume":"9294","author":"F B\u00f6kler","year":"2015","unstructured":"B\u00f6kler, F., Mutzel, P.: Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. Lect. Notes Comput. Sci. 9294, 288\u2013299 (2015)","journal-title":"Lect. Notes Comput. Sci."},{"key":"251_CR6","first-page":"376","volume":"23","author":"A Cayley","year":"1889","unstructured":"Cayley, A.: A theorem on trees. Q. J. Math. 23, 376\u2013378 (1889)","journal-title":"Q. J. Math."},{"issue":"6","key":"251_CR7","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"251_CR8","doi-asserted-by":"crossref","unstructured":"Chou, W., Kershenbaum, A.: A unified algorithm for designing multidrop teleprocessing networks. In: Proceedings of the Third ACM Symposium on Data Communications and Data Networks: Analysis and Design, DATACOMM \u201973, pp. 148\u2013156. ACM, NY (1973)","DOI":"10.1145\/800280.811042"},{"issue":"3","key":"251_CR9","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF00938448","volume":"45","author":"HW Corley","year":"1985","unstructured":"Corley, H.W.: Efficient spanning trees. J. Optim. Theory Appl. 45(3), 481\u2013485 (1985)","journal-title":"J. Optim. Theory Appl."},{"key":"251_CR10","unstructured":"Ehrgott, M.: Multicriteria optimization. In: Lecture Notes in Economics and Mathematical Systems, volume 491, 2nd edn. Springer, Berlin (2005)"},{"issue":"1","key":"251_CR11","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0377-2217(96)00116-6","volume":"97","author":"M Ehrgott","year":"1997","unstructured":"Ehrgott, M., Klamroth, K.: Connectedness of efficient solutions in multiple criteria combinatorial optimization. Eur. J. Oper. Res. 97(1), 159\u2013166 (1997)","journal-title":"Eur. J. Oper. Res."},{"key":"251_CR12","unstructured":"Eppstein, D.: Representing All Minimum Spanning Trees with Applications to Counting and Generation. Technical Report 95-50, University of California, Irvine, Department of Information and Computer Science,, California (1995)"},{"issue":"3","key":"251_CR13","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1147\/sj.53.0142","volume":"5","author":"LR Esau","year":"1966","unstructured":"Esau, L.R., Williams, K.C.: On teleprocessing system design: part ii a method for approximating the optimal network. IBM Syst. J. 5(3), 142\u2013147 (1966)","journal-title":"IBM Syst. J."},{"issue":"1","key":"251_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10589-013-9551-x","volume":"56","author":"J Figueira","year":"2013","unstructured":"Figueira, J., Paquete, L., Simes, M.A.M., Vanderpooten, D.: Algorithmic improvements on dynamic programming for the bi-objective 0,1 knapsack problem. Comput. Optim. Appl. 56(1), 97\u2013111 (2013)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"251_CR15","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/0022-247X(68)90201-1","volume":"22","author":"AM Geoffrion","year":"1968","unstructured":"Geoffrion, A.M.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22(3), 618\u2013630 (1968)","journal-title":"J. Math. Anal. Appl."},{"key":"251_CR16","unstructured":"Gorski, J.: Multiple Objective Optimization and its Implications to Single Objective Optimization Problems. Ph.D. Thesis, University of Wuppertal, Germany (2010)"},{"issue":"3","key":"251_CR17","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s10957-011-9849-8","volume":"150","author":"J Gorski","year":"2011","unstructured":"Gorski, J., Klamroth, K., Ruzika, S.: Connectedness of efficient solutions in multiple objective combinatorial optimization. J. Optim. Theory Appl. 150(3), 475\u2013497 (2011)","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"251_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02032304","volume":"52","author":"HW Hamacher","year":"1994","unstructured":"Hamacher, H.W., Ruhe, G.: On spanning tree problems with multiple objectives. Ann. Oper. Res. 52(4), 209\u2013230 (1994)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"251_CR19","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1137\/S009753979225030X","volume":"24","author":"S Kapoor","year":"1995","unstructured":"Kapoor, S., Ramesh, H.: Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM J. Comput. 24(2), 247\u2013265 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"251_CR20","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321\u2013328 (1995)","journal-title":"J. ACM"},{"key":"251_CR21","doi-asserted-by":"crossref","unstructured":"Knowles, J.D., Corne, D.W.: A Comparison of Encodings and Algorithms for Multi-objective Minimum Spanning Tree Problems, volume 1, pp. 544\u2013551. IEEE Press, Piscataway (2001)","DOI":"10.1109\/CEC.2001.934439"},{"issue":"1","key":"251_CR22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"251_CR23","unstructured":"Lacour, R.: Exact and Approximate Solving Approaches in Multi-objective Combinatorial Optimization, Application to the Minimum Weight Spanning Tree Problem. Ph.D. Thesis, Universit\u00e9 Paris-Dauphine, France (2014)"},{"issue":"4","key":"251_CR24","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1145\/320893.320896","volume":"4","author":"H Loberman","year":"1957","unstructured":"Loberman, H., Weinberger, A.: Formal procedures for connecting terminals with a minimum total wire length. J. ACM 4(4), 428\u2013437 (1957)","journal-title":"J. ACM"},{"key":"251_CR25","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1287\/mnsc.1100.1248","volume":"56","author":"\u00d6 \u00d6zpeynirci","year":"2010","unstructured":"\u00d6zpeynirci, \u00d6., K\u00f6ksalan, M.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manag. Sci. 56, 2302\u20132315 (2010)","journal-title":"Manag. Sci."},{"key":"251_CR26","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Technol. J. 36, 1389\u20131401 (1957)","journal-title":"Bell Syst. Technol. J."},{"issue":"3","key":"251_CR27","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1287\/ijoc.1090.0342","volume":"22","author":"A Przybylski","year":"2009","unstructured":"Przybylski, A., Gandibleux, X., Ehrgott, M.: A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3), 371\u2013386 (2009)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"251_CR28","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s11590-014-0759-1","volume":"9","author":"LP Pugliese","year":"2015","unstructured":"Pugliese, L.P., Guerriero, F., Santos, J.L.: Dynamic programming for spanning tree problems: application to the multi-objective case. Optim. Lett. 9(3), 437\u2013450 (2015)","journal-title":"Optim. Lett."},{"issue":"3","key":"251_CR29","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/S0377-2217(97)00391-3","volume":"111","author":"RM Ramos","year":"1998","unstructured":"Ramos, R.M., Alonso, S., Sicilia, J., Gonz\u00e1lez, C.: The problem of the optimal biobjective spanning tree. Eur. J. Oper. Res. 111(3), 617\u2013628 (1998)","journal-title":"Eur. J. Oper. Res."},{"key":"251_CR30","volume-title":"A Cost Analysis of Minimum Distance TV Networking for Broadcasting Medical Information","author":"JA Rossi","year":"1970","unstructured":"Rossi, J.A., Heiser, R.S., King, N.S.: A Cost Analysis of Minimum Distance TV Networking for Broadcasting Medical Information. Rand Corporation, Santa Monica (1970)"},{"key":"251_CR31","first-page":"104","volume-title":"A Survey on Multiple Objective Minimum Spanning Tree Problems","author":"S Ruzika","year":"2009","unstructured":"Ruzika, S., Hamacher, H.W.: A Survey on Multiple Objective Minimum Spanning Tree Problems, pp. 104\u2013116. Springer, Berlin (2009)"},{"key":"251_CR32","doi-asserted-by":"crossref","unstructured":"Saltman, R.G., Bolotsky, G.R., Ruthberg, Z.G.: Heuristic cost optimization of the federal telpak network. In: United States Department of Commerce. National Bureau of Standards. Technical note. U.S. National Bureau of Standards (1973)","DOI":"10.6028\/NBS.TN.787"},{"key":"251_CR33","unstructured":"Seipp, F.: On Adjacency, Cardinality, and Partial Dominance in Discrete Multiple Objective Optimization. Ph.D. Thesis, Technische Universit\u00e4t Kaiserslauern, Germany (2013)"},{"issue":"3","key":"251_CR34","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1287\/ijoc.1070.0260","volume":"20","author":"F Sourd","year":"2008","unstructured":"Sourd, F., Spanjaard, O.: A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem. INFORMS J. Comput. 20(3), 472\u2013484 (2008)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"251_CR35","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.cor.2006.02.023","volume":"35","author":"S Steiner","year":"2008","unstructured":"Steiner, S., Radzik, T.: Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. 35(1), 198\u2013211 (2008)","journal-title":"Comput. Oper. Res."},{"key":"251_CR36","volume-title":"Multiple Criteria Optimization: Theory, Computation, and Application","author":"R Steuer","year":"1989","unstructured":"Steuer, R.: Multiple Criteria Optimization: Theory, Computation, and Application. Robert E. Krieger Publishing Company, Malabar (1989)"},{"key":"251_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1","volume-title":"Algorithms on Trees and Graphs","author":"G Valiente","year":"2002","unstructured":"Valiente, G.: Algorithms on Trees and Graphs. Springer, Secaucus (2002)"},{"key":"251_CR38","doi-asserted-by":"publisher","DOI":"10.1201\/9780203497289","volume-title":"Spanning Trees and Optimization Problems","author":"BY Wu","year":"2004","unstructured":"Wu, B.Y., Chao, K.: Spanning Trees and Optimization Problems. Chapman & Hall\/CRC, Boca Raton (2004)"},{"issue":"1","key":"251_CR39","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0377-2217(98)00016-2","volume":"114","author":"G Zhou","year":"1999","unstructured":"Zhou, G., Gen, M.: Genetic algorithm approach on multi-criteria minimum spanning tree problem. Eur. J. Oper. Res. 114(1), 141\u2013152 (1999)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00251-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00251-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00251-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T23:03:01Z","timestamp":1724367781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00251-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,25]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["251"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00251-6","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,25]]},"assertion":[{"value":"13 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}