{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T22:56:53Z","timestamp":1787612213029,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032091192","type":"print"},{"value":"9783032091208","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T00:00:00Z","timestamp":1763510400000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-09120-8_9","type":"book-chapter","created":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:52:20Z","timestamp":1763466740000},"page":"119-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Graph Traversal via\u00a0Connected Mobile Agents"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3238-8233","authenticated-orcid":false,"given":"Saswata","family":"Jana","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9492-9894","authenticated-orcid":false,"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8632-5767","authenticated-orcid":false,"given":"Partha Sarathi","family":"Mandal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,11,19]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1287\/moor.23.3.640","volume":"23","author":"EM Arkin","year":"1998","unstructured":"Arkin, E.M., Hassin, R.: On local search for weighted k-set packing. Math. Oper. Res. 23(3), 640\u2013648 (1998)","journal-title":"Math. Oper. Res."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean tsp and other geometric problems. In: Proceedings of 37th Conference on Foundations of Computer Science, pp. 2\u201311. IEEE (1996)","DOI":"10.1109\/SFCS.1996.548458"},{"issue":"2","key":"9_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1006\/jagm.2000.1155","volume":"39","author":"B Chandra","year":"2001","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Greedy local improvement and weighted set packing approximation. J. Algorithms 39(2), 223\u2013240 (2001)","journal-title":"J. Algorithms"},{"key":"9_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2021.100369","volume":"40","author":"O Cheikhrouhou","year":"2021","unstructured":"Cheikhrouhou, O., Khoufi, I.: A comprehensive survey on the multiple traveling salesman problem: applications, approaches and taxonomy. Comput. Sci. Rev. 40, 100369 (2021)","journal-title":"Comput. Sci. Rev."},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s43069-021-00101-z","volume":"3","author":"N Christofides","year":"2022","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3(1), 1\u20134 (2022). https:\/\/doi.org\/10.1007\/s43069-021-00101-z","journal-title":"Oper. Res. Forum"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s00493-010-2341-5","volume":"30","author":"ED Demaine","year":"2010","unstructured":"Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. Combinatorica 30, 533\u2013552 (2010)","journal-title":"Combinatorica"},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/110820774","volume":"41","author":"Y Emek","year":"2012","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728\u2013746 (2012)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0203017","volume":"3","author":"SE Goodman","year":"1974","unstructured":"Goodman, S.E., Hedetniemi, S.T.: On Hamiltonian walks in graphs. SIAM J. Comput. 3(3), 214\u2013221 (1974)","journal-title":"SIAM J. Comput."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph tsp. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 640\u2013645. IEEE (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"issue":"5","key":"9_CR10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.: Analysis of christofides\u2019 heuristic: some paths are more difficult than cycles. Oper. Res. Lett. 10(5), 291\u2013295 (1991). https:\/\/doi.org\/10.1016\/0167-6377(91)90016-I","journal-title":"Oper. Res. Lett."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Jana, S., Italiano, G.F., Mandal, P.S.: Graph traversal via connected mobile agents (2025). https:\/\/arxiv.org\/abs\/2508.18683","DOI":"10.1007\/978-3-032-09120-8_9"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 32\u201345 (2021)","DOI":"10.1145\/3406325.3451009"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pp. 219\u2013241. Springer, Cham (2009)","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Klein, P.N.: A linear-time approximation scheme for planar weighted tsp. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 647\u2013656. IEEE (2005)","DOI":"10.1109\/SFCS.2005.7"},{"issue":"4","key":"9_CR15","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JS Mitchell","year":"1999","unstructured":"Mitchell, J.S.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9_CR16","first-page":"76","volume":"17","author":"AI Serdyukov","year":"1978","unstructured":"Serdyukov, A.I.: O nekotorykh ekstremal\u2019nykh obkhodakh v grafakh. Upravlyayemyye sistemy 17, 76\u201379 (1978)","journal-title":"Upravlyayemyye sistemy"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Sviridenko, M., Ward, J.: Large neighborhood local search for the maximum set packing problem. In: International Colloquium on Automata, Languages, and Programming. pp. 792\u2013803. Springer, Cham (2013)","DOI":"10.1007\/978-3-642-39206-1_67"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Thiery, T., Ward, J.: An improved approximation for maximum weighted k-set packing. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1138\u20131162. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch42"},{"issue":"3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10898-011-9726-x","volume":"53","author":"W Zhang","year":"2012","unstructured":"Zhang, W., Wu, W., Lee, W., Du, D.Z.: Complexity and approximation of the connected set-cover problem. J. Global Optim. 53(3), 563\u2013572 (2012)","journal-title":"J. Global Optim."}],"container-title":["Lecture Notes in Computer Science","Algorithmics of Wireless Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-09120-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T10:52:54Z","timestamp":1787568774000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-09120-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,19]]},"ISBN":["9783032091192","9783032091208"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-09120-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,19]]},"assertion":[{"value":"19 November 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ALGOWIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmics of Wireless Networks","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","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":"18 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"algosensors2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}