{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:20Z","timestamp":1740108260512,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T00:00:00Z","timestamp":1707955200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T00:00:00Z","timestamp":1707955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016379","name":"Universit\u00e4t Osnabr\u00fcck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016379","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we take an in-depth look at the complexity of a hitherto unexplored <jats:italic>multiobjective minimum weight minimum stretch spanner<\/jats:italic> problem; or in short <jats:italic>multiobjective spanner (MSp)<\/jats:italic> problem. The MSp is a multiobjective generalization of the well-studied minimum t-spanner problem. This multiobjective approach allows to find solutions that offer a viable compromise between cost and utility\u2014a property that is usually neglected in singleobjective optimization. Thus, the MSp can be a powerful modeling tool when it comes to, e.g., the planning of transportation or communication networks. This holds especially in disaster management, where both responsiveness and practicality are crucial. We show that for degree-3 bounded outerplanar instances the MSp is intractable and computing the non-dominated set is <jats:bold>BUCO<\/jats:bold>-hard. Additionally, we prove that if <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textbf{P}} \\ne \\textbf{NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mo>\u2260<\/mml:mo>\n                    <mml:mi>NP<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the set of extreme points cannot be computed in output-polynomial time, for instances with unit costs and arbitrary graphs. Furthermore, we consider the directed versions of the cases above.<\/jats:p>","DOI":"10.1007\/s00186-024-00850-7","type":"journal-article","created":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T20:02:21Z","timestamp":1708027341000},"page":"65-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of the multiobjective minimum weight minimum stretch spanner problem"],"prefix":"10.1007","volume":"100","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7950-6965","authenticated-orcid":false,"given":"Fritz","family":"B\u00f6kler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9821-8600","authenticated-orcid":false,"given":"Henning","family":"Jasper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,15]]},"reference":[{"key":"850_CR1","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/978-3-030-34029-2_35","volume-title":"Analysis of experimental algorithms","author":"R Ahmed","year":"2019","unstructured":"Ahmed R, Hamm K, Latifi Jebelli MJ et al (2019) Approximation algorithms and an integer program for multi-level graph spanners. In: Kotsireas I, Pardalos P, Parsopoulos KE et al (eds) Analysis of experimental algorithms. Springer, Cham, pp 541\u2013562"},{"issue":"1","key":"850_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer I, Das G, Dobkin D et al (1993) On sparse spanners of weighted graphs. Discrete Comput Geom 9(1):81\u2013100","journal-title":"Discrete Comput Geom"},{"key":"850_CR3","series-title":"Springer monographs in mathematics","volume-title":"Digraphs: theory, algorithms and applications","author":"J Bang-Jensen","year":"2008","unstructured":"Bang-Jensen J, Gutin G (2008) Digraphs: theory, algorithms and applications, 2nd edn. Springer monographs in mathematics. Springer, London","edition":"2"},{"issue":"4","key":"850_CR4","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana S, Sen S (2007) A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct Algorithms 30(4):532\u2013563","journal-title":"Random Struct Algorithms"},{"key":"850_CR5","unstructured":"B\u00f6kler F (2018) Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem. PhD thesis, Technische Universit\u00e4t Dortmund"},{"issue":"1\u20132","key":"850_CR6","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/mcda.1603","volume":"24","author":"F B\u00f6kler","year":"2017","unstructured":"B\u00f6kler F, Ehrgott M, Morris C et al (2017) Output-sensitive complexity of multiobjective combinatorial optimization. J Multi-Criteria Decis Anal 24(1\u20132):25\u201336","journal-title":"J Multi-Criteria Decis Anal"},{"issue":"1","key":"850_CR7","doi-asserted-by":"publisher","first-page":"76","DOI":"10.4230\/DagRep.10.1.52","volume":"10","author":"F B\u00f6kler","year":"2020","unstructured":"B\u00f6kler F, Ehrgott M, Rui Figueira J et al (2020) The output-sensitive complexity of the BUCO problem. Dagstuhl Rep 10(1):76\u201378. https:\/\/doi.org\/10.4230\/DagRep.10.1.52","journal-title":"Dagstuhl Rep"},{"key":"850_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6kler F, Mutzel P (2015) Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. Algorithms\u2014ESA 2015. Springer, Berlin, pp 288\u2013299","DOI":"10.1007\/978-3-662-48350-3_25"},{"key":"850_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6kler F, Chimani M (2020) Approximating multiobjective shortest path in practice. In: SIAM ALENEX, pp 120\u2013133","DOI":"10.1137\/1.9781611976007.10"},{"issue":"1","key":"850_CR10","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2699445","volume":"62","author":"T Brunsch","year":"2015","unstructured":"Brunsch T, R\u00f6glin H (2015) Improved smoothed analysis of multiobjective optimization. J ACM 62(1):4:1-4:58","journal-title":"J ACM"},{"issue":"2","key":"850_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","volume":"48","author":"L Cai","year":"1994","unstructured":"Cai L (1994) NP-completeness of minimum spanner problems. Discrete Appl Math 48(2):187\u2013194. https:\/\/doi.org\/10.1016\/0166-218X(94)90073-6","journal-title":"Discrete Appl Math"},{"issue":"4","key":"850_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/net.3230240406","volume":"24","author":"L Cai","year":"1994","unstructured":"Cai L, Keil M (1994) Spanners in graphs of bounded degree. Networks 24(4):233\u2013249. https:\/\/doi.org\/10.1002\/net.3230240406","journal-title":"Networks"},{"issue":"3","key":"850_CR13","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S08954801922374033","volume":"8","author":"L Cai","year":"1995","unstructured":"Cai L, Corneil D (1995) Tree spanners. SIAM J Discrete Math 8(3):359\u2013387. https:\/\/doi.org\/10.1137\/S08954801922374033","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"850_CR14","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.seps.2011.04.004","volume":"46","author":"A Caunhye","year":"2012","unstructured":"Caunhye A, Nie X, Pokharel S (2012) Optimization models in emergency logistics: a literature review. Socioecon Plann Sci 46(1):4\u201313","journal-title":"Socioecon Plann Sci"},{"key":"850_CR15","doi-asserted-by":"publisher","unstructured":"Cook S (1971) The complexity of theorem-proving procedures. In: ACM STOC, pp 151\u2013158. https:\/\/doi.org\/10.1145\/800157.805047","DOI":"10.1145\/800157.805047"},{"issue":"3","key":"850_CR16","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1287\/trsc.2014.0534","volume":"49","author":"D Delling","year":"2015","unstructured":"Delling D, Pajor T, Werneck R (2015) Round-based public transit routing. Transp Sci 49(3):591\u2013604","journal-title":"Transp Sci"},{"key":"850_CR17","series-title":"Graduate texts in mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph theory","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory, vol 173. Graduate texts in mathematics. Springer, Berlin"},{"key":"850_CR18","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization. Springer, Berlin"},{"issue":"5","key":"850_CR19","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1515\/dma.1992.2.5.461","volume":"2","author":"V Emelichev","year":"1992","unstructured":"Emelichev V, Perepelitsa V (1992) On cardinality of the set of alternatives in discrete many-criterion problems. Discrete Math Appl 2(5):461\u2013471","journal-title":"Discrete Math Appl"},{"issue":"1","key":"850_CR20","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ijrobp.2013.05.013","volume":"87","author":"D Giantsoudi","year":"2013","unstructured":"Giantsoudi D, Grassberger C, Craft D et al (2013) Linear energy transfer-guided optimization in intensity modulated proton therapy: feasibility study and clinical potential. Int J Radiat Oncol Biol Phys 87(1):216\u2013222","journal-title":"Int J Radiat Oncol Biol Phys"},{"issue":"4","key":"850_CR21","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02032304","volume":"52","author":"H Hamacher","year":"1994","unstructured":"Hamacher H, Ruhe G (1994) On spanning tree problems with multiple objectives. Ann Oper Res 52(4):209\u2013230","journal-title":"Ann Oper Res"},{"key":"850_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1142\/9789812817839_0016","volume-title":"Inverse radiation therapy planning: a multiple objective optimisation approach. Monitoring evaluating. Planning health services","author":"H Hamacher","year":"1999","unstructured":"Hamacher H, K\u00fcfer K (1999) Inverse radiation therapy planning: a multiple objective optimisation approach. Monitoring evaluating. Planning health services. World Scientific, Singapore, pp 177\u2013189"},{"key":"850_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-48782-8_9","volume-title":"Bicriterion path problems. Multiple criteria decision making theory and application","author":"P Hansen","year":"1980","unstructured":"Hansen P (1980) Bicriterion path problems. Multiple criteria decision making theory and application, vol 177. Springer, Berlin, pp 109\u2013127"},{"issue":"3","key":"850_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson DS, Yannakakis M, Papadimitriou CH (1988) On generating all maximal independent sets. Inf Process Lett 27(3):119\u2013123","journal-title":"Inf Process Lett"},{"key":"850_CR25","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2018.06.031","volume":"746","author":"Y Kobayashi","year":"2018","unstructured":"Kobayashi Y (2018) NP-hardness and fixed-parameter tractability of the minimum spanner problem. Theoret Comput Sci 746:88\u201397. https:\/\/doi.org\/10.1016\/j.tcs.2018.06.031","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"850_CR26","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1994.1032","volume":"17","author":"G Kortsarz","year":"1994","unstructured":"Kortsarz G, Peleg D (1994) Generating sparse 2-spanners. J Algorithms 17(2):222\u2013236","journal-title":"J Algorithms"},{"key":"850_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.cmpb.2020.105664","volume":"196","author":"G Libotte","year":"2020","unstructured":"Libotte G, Lobato F, Platt G et al (2020) Determination of an optimal control strategy for vaccine administration in COVID-19 pandemic treatment. Comput Methods Programs Biomed 196:105664","journal-title":"Comput Methods Programs Biomed"},{"key":"850_CR28","doi-asserted-by":"publisher","unstructured":"Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: 41st IEEE FoCS, pp 86\u201392. https:\/\/doi.org\/10.1109\/SFCS.2000.892068","DOI":"10.1109\/SFCS.2000.892068"},{"issue":"1","key":"850_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg D, Sch\u00e4ffer A (1989) Graph spanners. J Graph Theory 13(1):99\u2013116","journal-title":"J Graph Theory"},{"issue":"4","key":"850_CR30","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg D, Ullman J (1989) An optimal synchronizer for the hypercube. SIAM J Comput 18(4):740\u2013747","journal-title":"SIAM J Comput"},{"key":"850_CR31","doi-asserted-by":"crossref","unstructured":"Sigurd M, Zachariasen M (2004) Construction of minimum-weight spanners. Algorithms\u2014ESA 2004. Springer, Berlin, pp 797\u2013808","DOI":"10.1007\/978-3-540-30140-0_70"},{"issue":"2","key":"850_CR32","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/j.radonc.2007.06.020","volume":"85","author":"C Thieke","year":"2007","unstructured":"Thieke C, K\u00fcfer K, Monz M et al (2007) A new concept for interactive radiotherapy planning with multicriteria optimization: first clinical evaluation. Radiother Oncol 85(2):292\u2013298","journal-title":"Radiother Oncol"},{"key":"850_CR33","unstructured":"Wagner D, Z\u00fcndorf T (2017) Public transit routing with unrestricted walking. In: ATMOS 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-024-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-024-00850-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-024-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T09:05:39Z","timestamp":1725267939000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-024-00850-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,15]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["850"],"URL":"https:\/\/doi.org\/10.1007\/s00186-024-00850-7","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2024,2,15]]},"assertion":[{"value":"7 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Both authors were funded by Osnabr\u00fcck University, Germany. There are no further conflicts of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}}]}}