{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:29:59Z","timestamp":1763468999408,"version":"3.43.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826696"},{"type":"electronic","value":"9783031826702"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_12","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:39:36Z","timestamp":1738816776000},"page":"151-165","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Orienteering (with Time Windows) on\u00a0Restricted Graph Classes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3022-7877","authenticated-orcid":false,"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8591-3380","authenticated-orcid":false,"given":"Mart","family":"Hagedoorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7966-076X","authenticated-orcid":false,"given":"Guangping","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8788-1028","authenticated-orcid":false,"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/S12532-012-0047-Y","volume":"5","author":"HG Abeledo","year":"2013","unstructured":"Abeledo, H.G., Fukasawa, R., Pessoa, A.A., Uchoa, E.: The time dependent traveling salesman problem: polyhedra and algorithm. Math. Program. Comput. 5(1), 27\u201355 (2013). https:\/\/doi.org\/10.1007\/S12532-012-0047-Y","journal-title":"Math. Program. Comput."},{"key":"12_CR2","doi-asserted-by":"publisher","unstructured":"Archetti, C., Speranza, M.G., Vigo, D.: Vehicle routing problems with profits. In: Vehicle Routing: Problems, Methods, and Applications, 2nd edn., pp. 273\u2013297. SIAM (2014). https:\/\/doi.org\/10.1137\/1.9781611973594.ch10","DOI":"10.1137\/1.9781611973594.ch10"},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 13\u201316 June 2004, pp. 166\u2013174. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007385","DOI":"10.1145\/1007352.1007385"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M.T., Korula, N., Marx, D.: Prize-collecting Steiner problems on planar graphs. In: Proceedings of 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1028\u20131049. SIAM (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.79","DOI":"10.1137\/1.9781611973082.79"},{"issue":"4","key":"12_CR5","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/J.DISOPT.2008.04.001","volume":"5","author":"L Bigras","year":"2008","unstructured":"Bigras, L., Gamache, M., Savard, G.: The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Disc. Optim. 5(4), 685\u2013699 (2008). https:\/\/doi.org\/10.1016\/J.DISOPT.2008.04.001","journal-title":"Disc. Optim."},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37(2), 653\u2013670 (2007). https:\/\/doi.org\/10.1137\/050645464","journal-title":"SIAM J. Comput."},{"issue":"6","key":"12_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996). https:\/\/doi.org\/10.1137\/S0097539793251219","journal-title":"SIAM J. Comput."},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Buchin, K., Hagedoorn, M., Li, G.: Tour4me: a framework for customized tour planning algorithms. In: Proceedings of the 30th International Conference on Advances in Geographic Information Systems. SIGSPATIAL 2022. Association for Computing Machinery, New York (2022). https:\/\/doi.org\/10.1145\/3557915.3560992","DOI":"10.1145\/3557915.3560992"},{"key":"12_CR9","unstructured":"Buchin, K., Hagedoorn, M., Li, G., Rehs, C.: Orienteering (with time windows) on restricted graph classes (2024). https:\/\/arxiv.org\/abs\/2410.12401"},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2229163.2229167","volume":"8","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Korula, N., P\u00e1l, M.: Improved algorithms for orienteering and related problems. ACM Trans. Algor. (TALG) 8(3), 1\u201327 (2012). https:\/\/doi.org\/10.1145\/2229163.2229167","journal-title":"ACM Trans. Algor. (TALG)"},{"issue":"1","key":"12_CR11","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1137\/060667839","volume":"38","author":"K Chen","year":"2008","unstructured":"Chen, K., Har-Peled, S.: The euclidean orienteering problem revisited. SIAM J. Comput. 38(1), 385\u2013397 (2008). https:\/\/doi.org\/10.1137\/060667839","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1287\/trsc.1030.0079","volume":"39","author":"D Feillet","year":"2005","unstructured":"Feillet, D., Dejax, P., Gendreau, M.: Traveling salesman problems with profits. Transp. Sci. 39(2), 188\u2013205 (2005). https:\/\/doi.org\/10.1287\/trsc.1030.0079","journal-title":"Transp. Sci."},{"issue":"2","key":"12_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/ijoc.10.2.133","volume":"10","author":"M Fischetti","year":"1998","unstructured":"Fischetti, M., Gonzalez, J.J., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. 10(2), 133\u2013148 (1998). https:\/\/doi.org\/10.1287\/ijoc.10.2.133","journal-title":"INFORMS J. Comput."},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Garg, N., Khanna, S., Kumar, A.: Hardness of approximation for orienteering with multiple time windows. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2977\u20132990. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.177","DOI":"10.1137\/1.9781611976465.177"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.ipl.2014.10.003","volume":"115","author":"D Gavalas","year":"2015","unstructured":"Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., Vathis, N.: Approximation algorithms for the arc orienteering problem. Inf. Process. Lett. 115(2), 313\u2013315 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2014.10.003","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"BL Golden","year":"1987","unstructured":"Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logist. (NRL) 34(3), 307\u2013318 (1987). https:\/\/doi.org\/10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","journal-title":"Naval Res. Logist. (NRL)"},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/J.EJOR.2016.04.059","volume":"255","author":"A Gunawan","year":"2016","unstructured":"Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: a survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2), 315\u2013332 (2016). https:\/\/doi.org\/10.1016\/J.EJOR.2016.04.059","journal-title":"Eur. J. Oper. Res."},{"key":"12_CR18","unstructured":"Korula, N.: Approximation algorithms for network design and orienteering. University of Illinois at Urbana-Champaign (2010). https:\/\/www.ideals.illinois.edu\/items\/16799"},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Korula, N.: Orienteering problems. In: Encyclopedia of Algorithms, pp. 1481\u20131484. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_540","DOI":"10.1007\/978-1-4939-2864-4_540"},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(90)90100-Q","volume":"26","author":"G Laporte","year":"1990","unstructured":"Laporte, G., Martello, S.: The selective travelling salesman problem. Disc. Appl. Math. 26(2), 193\u2013207 (1990). https:\/\/doi.org\/10.1016\/0166-218X(90)90100-Q","journal-title":"Disc. Appl. Math."},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Lu, Y., et al.: Scenic routes now: efficiently solving the time-dependent arc orienteering problem. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 487\u2013496 (2017). https:\/\/doi.org\/10.1145\/3132847.3132874","DOI":"10.1145\/3132847.3132874"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Lu, Y., Shahabi, C.: An arc orienteering algorithm to find the most scenic path on a large-scale road network. In: Proceedings of 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1\u201310 (2015). https:\/\/doi.org\/10.1145\/2820783.2820835","DOI":"10.1145\/2820783.2820835"},{"issue":"2","key":"12_CR23","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1287\/ijoc.4.2.155","volume":"4","author":"R Ramesh","year":"1992","unstructured":"Ramesh, R., Yoon, Y.S., Karwan, M.H.: An optimal algorithm for the orienteering tour problem. ORSA J. Comput. 4(2), 155\u2013165 (1992). https:\/\/doi.org\/10.1287\/ijoc.4.2.155","journal-title":"ORSA J. Comput."},{"key":"12_CR24","unstructured":"Ren, K., Salavatipour, M.R.: Approximation schemes for orienteering and deadline tsp in doubling metrics. arXiv preprint arXiv:2405.00818 (2024)"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Souffriau, W., Vansteenwegen, P., Vertommen, J., Vanden\u00a0Berghe, G.: A personalized tourist trip design algorithm for mobile tourist guides. Appl. Artif. Intell. 22, 964\u2013985 (2008). https:\/\/doi.org\/10.1080\/08839510802379626","DOI":"10.1080\/08839510802379626"},{"issue":"1","key":"12_CR26","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/j.ejor.2018.09.046","volume":"274","author":"F Stavropoulou","year":"2019","unstructured":"Stavropoulou, F., Repoussis, P.P., Tarantilis, C.D.: The vehicle routing problem with profits and consistency constraints. Eur. J. Oper. Res. 274(1), 340\u2013356 (2019). https:\/\/doi.org\/10.1016\/j.ejor.2018.09.046","journal-title":"Eur. J. Oper. Res."},{"issue":"9","key":"12_CR27","doi-asserted-by":"publisher","first-page":"797","DOI":"10.2307\/2582629","volume":"35","author":"T Tsiligirides","year":"1984","unstructured":"Tsiligirides, T.: Heuristic methods applied to orienteering. J. Oper. Res. Soc. 35(9), 797\u2013809 (1984). https:\/\/doi.org\/10.2307\/2582629","journal-title":"J. Oper. Res. Soc."},{"issue":"3","key":"12_CR28","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/NET.3230220305","volume":"22","author":"JN Tsitsiklis","year":"1992","unstructured":"Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22(3), 263\u2013282 (1992). https:\/\/doi.org\/10.1002\/NET.3230220305","journal-title":"Networks"},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","volume":"209","author":"P Vansteenwegen","year":"2011","unstructured":"Vansteenwegen, P., Souffriau, W., Oudheusden, D.V.: The orienteering problem: a survey. Eur. J. Oper. Res. 209(1), 1\u201310 (2011). https:\/\/doi.org\/10.1016\/j.ejor.2010.03.045","journal-title":"Eur. J. Oper. Res."},{"key":"12_CR30","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1057\/ori.2007.17","volume":"20","author":"P Vansteenwegen","year":"2007","unstructured":"Vansteenwegen, P., Van Oudheusden, D.: The mobile tourist guide: an or opportunity. OR insight 20, 21\u201327 (2007). https:\/\/doi.org\/10.1057\/ori.2007.17","journal-title":"OR insight"},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tre.2014.05.006","volume":"68","author":"C Verbeeck","year":"2014","unstructured":"Verbeeck, C., Vansteenwegen, P., Aghezzaf, E.H.: An extension of the arc orienteering problem and its application to cycle trip planning. Transp. Res. Part E 68, 64\u201378 (2014). https:\/\/doi.org\/10.1016\/j.tre.2014.05.006","journal-title":"Transp. Res. Part E"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T15:26:11Z","timestamp":1754407571000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}