{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T12:12:27Z","timestamp":1763727147139},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319541563"},{"type":"electronic","value":"9783319541570"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-54157-0_6","type":"book-chapter","created":{"date-parts":[[2017,2,18]],"date-time":"2017-02-18T03:11:54Z","timestamp":1487387514000},"page":"77-87","source":"Crossref","is-referenced-by-count":7,"title":["The Multiobjective Shortest Path Problem Is NP-Hard, or Is It?"],"prefix":"10.1007","author":[{"given":"Fritz","family":"B\u00f6kler","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,19]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity - A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-540-72792-7_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Beier","year":"2007","unstructured":"Beier, R., R\u00f6glin, H., V\u00f6cking, B.: The smoothed number of Pareto optimal solutions in bicriteria integer optimization. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 53\u201367. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-72792-7_5"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6kler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity for multiobjective combinatorial optimization. J. Multi-Criteria Decis. Anal. (2017, accepted)","DOI":"10.1002\/mcda.1603"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-662-48350-3_25","volume-title":"Algorithms \u2013 ESA 2015","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. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 288\u2013299. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_25"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Brunsch, T., R\u00f6glin, H.: Improved smoothed analysis of multiobjective optimization. In: ACM SToC. pp. 407\u2013426 (2012)","DOI":"10.1145\/2213977.2214016"},{"key":"6_CR6","unstructured":"Galand, L., Ismaili, A., Perny, P., Spanjaard, O.: Bidirectional preference-based search for multiobjective state space graph problems. In: SoCS 2013 (2013)"},{"key":"6_CR7","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences, 1st edn. W. H. Freeman & Co., New York (1979)","edition":"1"},{"issue":"3","key":"6_CR8","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1023\/A:1012602011914","volume":"111","author":"F Guerriero","year":"2001","unstructured":"Guerriero, F., Musmanno, R.: Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111(3), 589\u2013613 (2001)","journal-title":"J. Optim. Theory Appl."},{"key":"6_CR9","series-title":"Lecture Notes in Economics and Mathematical Systems","first-page":"109","volume-title":"Multiple Criteria Decision Making Theory and Application","author":"P Hansen","year":"1979","unstructured":"Hansen, P.: Bicriterion path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making Theory and Application. Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 109\u2013127. Springer, New York (1979)"},{"issue":"3","key":"6_CR10","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1162\/EVCO_a_00014","volume":"18","author":"C Horoba","year":"2010","unstructured":"Horoba, C.: Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. Evol. Comput. 18(3), 357\u2013381 (2010)","journal-title":"Evol. Comput."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","volume":"16","author":"EQV Martins","year":"1984","unstructured":"Martins, E.Q.V.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 16, 236\u2013245 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"6_CR12","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/j.endm.2010.05.108","volume":"36","author":"C Mohamed","year":"2010","unstructured":"Mohamed, C., Bassem, J., Taicir, L.: A genetic algorithm to solve the bicriteria shortest path problem. Electr. Notes Discret. Math. 36, 851\u2013858 (2010)","journal-title":"Electr. Notes Discret. Math."},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74247-0_3","volume-title":"Algorithmic Methods for Railway Optimization","author":"M M\u00fcller-Hannemann","year":"2007","unstructured":"M\u00fcller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.: Timetable information: models and algorithms. In: Geraets, F., Kroon, F., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. LNCS, vol. 4359. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-74247-0_3"},{"issue":"9","key":"6_CR14","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1287\/mnsc.15.9.494","volume":"15","author":"GL Nemhauser","year":"1969","unstructured":"Nemhauser, G.L., Ullmann, Z.: Discrete dynamic programming and capital allocation. Manag. Sci. 15(9), 494\u2013505 (1969)","journal-title":"Manag. Sci."},{"issue":"4","key":"6_CR15","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1016\/j.cor.2008.02.002","volume":"36","author":"A Raith","year":"2009","unstructured":"Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res. 36(4), 1299\u20131331 (2009)","journal-title":"Comput. Oper. Res."},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Sanders, P., Mandow, L.: Parallel label-setting multi-objective shortest path search. In: Parallel & Distributed Processing (IPDPS), pp. 215\u2013224. IEEE (2013)","DOI":"10.1109\/IPDPS.2013.89"},{"key":"6_CR17","series-title":"Lecture Notes in Economics and Mathematical Systems","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-642-46618-2_15","volume-title":"Recent Advances and Historical Development of Vector Optimization","author":"P Serafini","year":"1986","unstructured":"Serafini, P.: Some considerations about computational complexity for multi-objective combinatorial problems. In: Jahn, J., Krabs, W. (eds.) Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294, pp. 222\u2013231. Springer, Heidelberg (1986). doi: 10.1007\/978-3-642-46618-2_15"},{"key":"6_CR18","unstructured":"Shekelyan, M., Joss\u00e9, G., Schubert, M.: Paretoprep: fast computation of path skyline queries. In: Advances in Spatial and Temporal Databases (2015)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-319-05810-8_12","volume-title":"Database Systems for Advanced Applications","author":"M Shekelyan","year":"2014","unstructured":"Shekelyan, M., Joss\u00e9, G., Schubert, M., Kriegel, H.-P.: Linear Path Skyline Computation in Bicriteria Networks. In: Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (eds.) DASFAA 2014. LNCS, vol. 8421, pp. 173\u2013187. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-05810-8_12"},{"key":"6_CR20","first-page":"199","volume":"17","author":"AJV Skriver","year":"2000","unstructured":"Skriver, A.J.V.: A classification of bicriterion shortest path algorithms. Asia-Pac. J. Oper. Res. 17, 199\u2013212 (2000)","journal-title":"Asia-Pac. J. Oper. Res."},{"issue":"2","key":"6_CR21","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2478\/v10006-007-0023-2","volume":"17","author":"Z Tarapata","year":"2007","unstructured":"Tarapata, Z.: Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms. Int. J. Appl. Math. Comput. Sci. 17(2), 269\u2013287 (2007)","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"6_CR22","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/11940128_40","volume":"4288","author":"G Tsaggouris","year":"2006","unstructured":"Tsaggouris, G., Zaroliagis, C.D.: Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications. Algorithms and Computation 4288, 389\u2013398 (2006)","journal-title":"Algorithms and Computation"},{"issue":"1","key":"6_CR23","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1287\/opre.35.1.70","volume":"35","author":"A Warburton","year":"1987","unstructured":"Warburton, A.: Approximation of Pareto optima in multiple-objective shortest-path problems. Oper. Res. 35(1), 70\u201379 (1987)","journal-title":"Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Evolutionary Multi-Criterion Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-54157-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T17:23:33Z","timestamp":1568827413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-54157-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319541563","9783319541570"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-54157-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}