{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:43:36Z","timestamp":1758267816346,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_32","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"442-456","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["How to Catch Marathon Cheaters: New\u00a0Approximation Algorithms for\u00a0Tracking\u00a0Paths"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[]},{"given":"Siddharth","family":"Gupta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3850-6739","authenticated-orcid":false,"given":"Hadi","family":"Khodabandeh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0664-9145","authenticated-orcid":false,"given":"Pedro","family":"Matias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,31]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: Ortiz, H. (ed.) STOC, pp. 293\u2013299. ACM (1990). https:\/\/doi.org\/10.1145\/100216.100254","DOI":"10.1145\/100216.100254"},{"issue":"1","key":"32_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994). https:\/\/doi.org\/10.1145\/174644.174650","journal-title":"J. ACM"},{"issue":"1","key":"32_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00453-019-00602-8","volume":"82","author":"A Banik","year":"2019","unstructured":"Banik, A., Choudhary, P., Lokshtanov, D., Raman, V., Saurabh, S.: A polynomial sized kernel for tracking paths problem. Algorithmica 82(1), 41\u201363 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00602-8","journal-title":"Algorithmica"},{"key":"32_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-57586-5_7","volume-title":"Algorithms and Complexity","author":"A Banik","year":"2017","unstructured":"Banik, A., Katz, M.J., Packer, E., Simakov, M.: Tracking paths. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 67\u201379. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57586-5_7"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2020.07.012","volume":"844","author":"D Bil\u00f2","year":"2020","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Tracking routes in communication networks. Theor. Comput. Sci. 844, 1\u201315 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.07.012","journal-title":"Theor. Comput. Sci."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-030-34029-2_7","volume-title":"Analysis of Experimental Algorithms","author":"G Borradaile","year":"2019","unstructured":"Borradaile, G., Le, H., Zheng, B.: Engineering a PTAS for minimum feedback vertex set in planar graphs. In: Kotsireas, I., Pardalos, P., Parsopoulos, K.E., Souravlias, D., Tsokas, A. (eds.) SEA 2019. LNCS, vol. 11544, pp. 98\u2013113. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34029-2_7"},{"issue":"4","key":"32_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discret. Comput. Geom. 14(4), 463\u2013479 (1995). https:\/\/doi.org\/10.1007\/BF02570718","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"32_CR8","first-page":"203","volume":"4","author":"N Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: Applications of the Lipton and Tarjan\u2019s planar separator theorem. J. Inf. Process 4(4), 203\u2013207 (1981)","journal-title":"J. Inf. Process"},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1109\/WPMC.2018.8713018","volume":"2018","author":"C Chokchai","year":"2018","unstructured":"Chokchai, C.: Low cost and high performance UHF RFID system using Arduino based on IoT applications for marathon competition. WPMC 2018, 15\u201320 (2018). https:\/\/doi.org\/10.1109\/WPMC.2018.8713018","journal-title":"WPMC"},{"key":"32_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-030-48966-3_13","volume-title":"Combinatorial Algorithms","author":"P Choudhary","year":"2020","unstructured":"Choudhary, P.: Polynomial time algorithms for tracking path problems. In: G\u0105sieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 166\u2013179. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48966-3_13"},{"key":"32_CR11","unstructured":"Choudhary, P., Raman, V.: Improved kernels for tracking path problems. CoRR abs\/2001.03161 (2020). http:\/\/arxiv.org\/abs\/2001.03161"},{"key":"32_CR12","unstructured":"Choudhary, P., Raman, V.: Structural parameterizations of tracking paths problem. In: Cordasco, G., Gargano, L., Rescigno, A.A. (eds.) CEUR. CEUR Workshop Proceedings, vol. 2756, pp. 15\u201327. CEUR-WS.org (2020)"},{"key":"32_CR13","unstructured":"Chung, F.R.: Separator theorems and their applications. Universit\u00e4t Bonn, Institut f\u00fcr \u00d6konometrie und Operations Research (1988)"},{"key":"32_CR14","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: SODA, pp. 590\u2013601. SIAM (2005)"},{"issue":"3","key":"32_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H Djidjev","year":"1997","unstructured":"Djidjev, H., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Informatica 34(3), 231\u2013243 (1997). https:\/\/doi.org\/10.1007\/s002360050082","journal-title":"Acta Informatica"},{"issue":"4","key":"32_CR16","first-page":"369","volume":"11","author":"HN Djidjev","year":"1985","unstructured":"Djidjev, H.N.: A linear algorithm for partitioning graphs of fixed genus. Serdica. Bulgariacae mathematicae publicationes 11(4), 369\u2013387 (1985)","journal-title":"Serdica. Bulgariacae mathematicae publicationes"},{"issue":"3","key":"32_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3), 275\u2013291 (2000). https:\/\/doi.org\/10.1007\/s004530010020","journal-title":"Algorithmica"},{"key":"32_CR18","doi-asserted-by":"publisher","unstructured":"Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: SIGSPATIAL. GIS, ACM (2008). https:\/\/doi.org\/10.1145\/1463434.1463455","DOI":"10.1145\/1463434.1463455"},{"key":"32_CR19","doi-asserted-by":"publisher","unstructured":"Eppstein, D., Goodrich, M.T., Liu, J.A., Matias, P.: Tracking paths in planar graphs. In: Lu, P., Zhang, G. (eds.) ISAAC. LIPIcs, vol. 149, pp. 54:1\u201354:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.54","DOI":"10.4230\/LIPIcs.ISAAC.2019.54"},{"key":"32_CR20","doi-asserted-by":"publisher","unstructured":"Eppstein, D., Gupta, S.: Crossing patterns in nonplanar road networks. In: SIGSPATIAL. GIS, ACM (2017). https:\/\/doi.org\/10.1145\/3139958.3139999","DOI":"10.1145\/3139958.3139999"},{"key":"32_CR21","unstructured":"Eppstein, D., Khodabandeh, H.: On the edge crossings of the greedy spanner. CoRR abs\/2002.05854 (2020). https:\/\/arxiv.org\/abs\/2002.05854"},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-1-4939-2864-4_47","volume-title":"Encyclopedia of Algorithms","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Demaine, E.D., Hajiaghayi, M.T., Thilikos, D.M.: Bidimensionality. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 203\u2013207. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_47"},{"issue":"6","key":"32_CR23","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987). https:\/\/doi.org\/10.1137\/0216064","journal-title":"SIAM J. Comput."},{"issue":"3","key":"32_CR24","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"JR Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms 5(3), 391\u2013407 (1984). https:\/\/doi.org\/10.1016\/0196-6774(84)90019-1","journal-title":"J. Algorithms"},{"issue":"3","key":"32_CR25","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1006\/jcss.1995.1076","volume":"51","author":"MT Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci. 51(3), 374\u2013389 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Gupta, S., Khodabandeh, H., Matias, P.: How to catch marathon cheaters: new approximation algorithms for tracking paths. CoRR abs\/2104.12337 (2021). https:\/\/arxiv.org\/abs\/2104.12337","DOI":"10.1007\/978-3-030-83508-8_32"},{"issue":"2","key":"32_CR27","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\epsilon $$-nets and simplex range queries. Discret. Comput. Geom. 2(2), 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/BF02187876","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"32_CR28","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"32_CR29","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980). https:\/\/doi.org\/10.1137\/0209046","journal-title":"SIAM J. Comput."},{"key":"32_CR30","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/978-1-4939-2864-4_526","volume-title":"Encyclopedia of Algorithms","author":"D Lokshtanov","year":"2016","unstructured":"Lokshtanov, D.: Kernelization, bidimensionality and kernels. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 1006\u20131011. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_526"},{"issue":"2","key":"32_CR31","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/BF01350657","volume":"178","author":"W Mader","year":"1968","unstructured":"Mader, W.: Homomorphies\u00e4tze f\u00fcr graphen. Math. Ann. 178(2), 154\u2013168 (1968)","journal-title":"Math. Ann."},{"key":"32_CR32","doi-asserted-by":"publisher","unstructured":"Reed, B.A., Wood, D.R.: A linear-time algorithm to find a separator in a graph excluding a minor. ACM Trans. Algorithms 5(4), 39:1\u201339:16 (2009). https:\/\/doi.org\/10.1145\/1597036.1597043","DOI":"10.1145\/1597036.1597043"},{"issue":"4","key":"32_CR33","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1112\/jlms\/s1-26.4.256","volume":"1","author":"P Ungar","year":"1951","unstructured":"Ungar, P.: A theorem on planar graphs. J. Lond. Math. Soc. 1(4), 256\u2013262 (1951)","journal-title":"J. Lond. Math. Soc."},{"key":"32_CR34","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-319-21852-6_3","volume-title":"Measures of Complexity","author":"VN Vapnik","year":"2015","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity, pp. 11\u201330. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21852-6_3"},{"key":"32_CR35","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"issue":"1","key":"32_CR36","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1109\/MPRV.2006.2","volume":"5","author":"R Want","year":"2006","unstructured":"Want, R.: An introduction to RFID technology. IEEE Pervasive Comput. 5(1), 25\u201333 (2006). https:\/\/doi.org\/10.1109\/MPRV.2006.2","journal-title":"IEEE Pervasive Comput."},{"key":"32_CR37","unstructured":"Wikipedia contributors: Marathon course-cutting (2019). https:\/\/en.wikipedia.org\/wiki\/Marathon_course-cutting. Accessed 16 Feb 2021"},{"key":"32_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"32_CR39","unstructured":"Zheng, B.: Approximation schemes in planar graphs. Ph.D. thesis, Oregon State University (2018). https:\/\/ir.library.oregonstate.edu\/concern\/graduate_thesis_or_dissertations\/7w62ff609. Accessed 07 Jan 2021"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:28:02Z","timestamp":1645183682000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"123","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}