{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T23:19:32Z","timestamp":1763767172204,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"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:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":180,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:sc>Minimum Eccentricity Shortest Path Problem<\/jats:sc> consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of distance to disjoint paths with the desired eccentricity, and maximum leaf number.\n<\/jats:p>","DOI":"10.1007\/978-3-030-79987-8_31","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"442-455","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2546-5344","authenticated-orcid":false,"given":"Martin","family":"Ku\u010dera","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7236-8336","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"31_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/978-3-319-48749-6_16","volume-title":"Combinatorial Optimization and Applications","author":"\u00c9 Birmel\u00e9","year":"2016","unstructured":"Birmel\u00e9, \u00c9., de Montgolfier, F., Planche, L.: Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 216\u2013229. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48749-6_16"},{"key":"31_CR2","unstructured":"Birmel\u00e9, E., de Montgolfier, F., Planche, L., Viennot, L.: Decomposing a graph into shortest paths with bounded eccentricity. In: ISAAC 2017. LIPIcs, vol. 92, pp. 15:1\u201315:13. Dagstuhl (2017)"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/j.dam.2020.03.060","volume":"284","author":"E Birmel\u00e9","year":"2020","unstructured":"Birmel\u00e9, E., de Montgolfier, F., Planche, L., Viennot, L.: Decomposing a graph into shortest paths with bounded eccentricity. Discrete Appl. Math. 284, 353\u2013374 (2020)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"key":"31_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"31_CR6","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory, 5th Edition, Graduate texts in mathematics, vol.\u00a0173. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-31940-7","DOI":"10.1007\/978-3-319-31940-7"},{"key":"31_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-319-21840-3_23","volume-title":"Algorithms and Data Structures","author":"FF Dragan","year":"2015","unstructured":"Dragan, F.F., Leitert, A.: On the minimum eccentricity shortest path problem. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 276\u2013288. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_23"},{"issue":"2","key":"31_CR8","doi-asserted-by":"publisher","first-page":"299","DOI":"10.7155\/jgaa.00394","volume":"20","author":"FF Dragan","year":"2016","unstructured":"Dragan, F.F., Leitert, A.: Minimum eccentricity shortest paths in some structured graph classes. J. Graph Algorithms Appl. 20(2), 299\u2013322 (2016)","journal-title":"J. Graph Algorithms Appl."},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2017.07.004","volume":"694","author":"FF Dragan","year":"2017","unstructured":"Dragan, F.F., Leitert, A.: On the minimum eccentricity shortest path problem. Theor. Comput. Sci. 694, 66\u201378 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: FOCS 2001, pp. 10\u201333. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959878"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Handbook of Discrete and Computational Geometry, pp. 177\u2013196. CRC Press, Boca Raton (2004)","DOI":"10.1201\/9781420035315.ch8"},{"key":"31_CR13","unstructured":"Ku\u010dera, M., Such\u00fd, O.: Minimum eccentricity shortest path problem with respect to structural parameters (2021). https:\/\/arxiv.org\/abs\/2008.07898"},{"key":"31_CR14","unstructured":"Sorge, M., Weller, M.: The graph parameter hierarchy (2016). https:\/\/manyu.pro\/assets\/parameter-hierarchy.pdf"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"Tenenbaum, J.B., Silva, V.D., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290(5500), 2319\u20132323 (2000)","DOI":"10.1126\/science.290.5500.2319"},{"key":"31_CR17","unstructured":"V\u00f6lkel, F., Bapteste, E., Habib, M., Lopez, P., Vigliotti, C.: Read networks and k-laminar graphs. CoRR abs\/1603.01179 (2016)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79987-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:16:05Z","timestamp":1625008565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_31","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":"30 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","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":"107","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":"38","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":"36% - 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":"9.1","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)"}},{"value":"The workshop was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}