{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:50:27Z","timestamp":1742914227585,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"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-75242-2_2","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"23-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Three Problems on Well-Partitioned Chordal Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0511-1976","authenticated-orcid":false,"given":"Jungho","family":"Ahn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-030-60440-0_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J Ahn","year":"2020","unstructured":"Ahn, J., Jaffke, L., Kwon, O., Lima, P.T.: Well-partitioned chordal graphs: obstruction set and disjoint paths. In: Adler, I., M\u00fcller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 148\u2013160. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-60440-0_12"},{"issue":"1","key":"2_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993). https:\/\/doi.org\/10.1007\/BF02189308","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"2_CR3","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1080\/00207160210954","volume":"79","author":"M Atici","year":"2002","unstructured":"Atici, M.: Computational complexity of geodetic set. Int. J. Comput. Math. 79(5), 587\u2013591 (2002). https:\/\/doi.org\/10.1080\/00207160210954","journal-title":"Int. J. Comput. Math."},{"issue":"3","key":"2_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1017\/S0963548304006145","volume":"13","author":"PN Balister","year":"2004","unstructured":"Balister, P.N., Gy\u00f6ri, E., Lehel, J., Schelp, R.H.: Longest paths in circular arc graphs. Comb. Probab. Comput. 13(3), 311\u2013317 (2004). https:\/\/doi.org\/10.1017\/S0963548304006145","journal-title":"Comb. Probab. Comput."},{"issue":"1\u20133","key":"2_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0304-3975(03)00424-9","volume":"310","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.O., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theoret. Comput. Sci. 310(1\u20133), 329\u2013354 (2004). https:\/\/doi.org\/10.1016\/S0304-3975(03)00424-9","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"2_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00453-006-1209-y","volume":"47","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H., Le, V.B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47(1), 27\u201351 (2007). https:\/\/doi.org\/10.1007\/s00453-006-1209-y","journal-title":"Algorithmica"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ipl.2018.02.012","volume":"135","author":"LR Bueno","year":"2018","unstructured":"Bueno, L.R., Penso, L.D., Protti, F., Ramos, V.R., Rautenbach, D., Souza, U.S.: On the hardness of finding the geodetic number of a subcubic graph. Inf. Process. Lett. 135, 22\u201327 (2018). https:\/\/doi.org\/10.1016\/j.ipl.2018.02.012","journal-title":"Inf. Process. Lett."},{"key":"2_CR8","unstructured":"Cai, L.: Tree spanners: spanning trees that approximate distances. Ph.D. thesis, University of Toronto (1992)"},{"issue":"3","key":"2_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8(3), 359\u2013387 (1995). https:\/\/doi.org\/10.1137\/S0895480192237403","journal-title":"SIAM J. Discrete Math."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.dam.2019.03.022","volume":"281","author":"MR Cerioli","year":"2020","unstructured":"Cerioli, M.R., Lima, P.T.: Intersection of longest paths in graph classes. Discrete Appl. Math. 281, 96\u2013105 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.03.022","journal-title":"Discrete Appl. Math."},{"key":"2_CR11","unstructured":"Chakraborty, D., Das, S., Foucaud, F., Gahlawat, H., Lajou, D., Roy, B.: Algorithms and complexity for geodetic sets on planar and chordal graphs. arXiv:2006.16511 (2020). To appear at ISAAC 2020"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-030-39219-2_9","volume-title":"Algorithms and Discrete Applied Mathematics","author":"D Chakraborty","year":"2020","unstructured":"Chakraborty, D., Foucaud, F., Gahlawat, H., Ghosh, S.K., Roy, B.: Hardness and approximation for the geodetic set problem in some graph classes. In: Changat, M., Das, S. (eds.) CALDAM 2020. LNCS, vol. 12016, pp. 102\u2013115. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-39219-2_9"},{"issue":"3","key":"2_CR13","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.disc.2016.07.023","volume":"340","author":"G Chen","year":"2017","unstructured":"Chen, G., et al.: Nonempty intersection of longest paths in series-parallel graphs. Discrete Math. 340(3), 287\u2013304 (2017). https:\/\/doi.org\/10.1016\/j.disc.2016.07.023","journal-title":"Discrete Math."},{"key":"2_CR14","first-page":"497","volume":"7","author":"MC Dourado","year":"2006","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: On the complexity of the geodetic and convexity numbers of a graph. Lect. Notes Ramanujan Math. Soc. 7, 497\u2013500 (2006)","journal-title":"Lect. Notes Ramanujan Math. Soc."},{"issue":"4","key":"2_CR15","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1016\/j.disc.2009.09.018","volume":"310","author":"MC Dourado","year":"2010","unstructured":"Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some remarks on the geodetic number of a graph. Discrete Math. 310(4), 832\u2013837 (2010)","journal-title":"Discrete Math."},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-29344-3_24","volume-title":"LATIN 2012: Theoretical Informatics","author":"T Ekim","year":"2012","unstructured":"Ekim, T., Erey, A., Heggernes, P., van \u2019t Hof, P., Meister, D.: Computing minimum geodetic sets of proper interval graphs. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 279\u2013290. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29344-3_24"},{"issue":"1\u20132","key":"2_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"SP Fekete","year":"2001","unstructured":"Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Appl. Math. 108(1\u20132), 85\u2013103 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00226-2","journal-title":"Discrete Appl. Math."},{"key":"2_CR18","unstructured":"Gallai, T.: Problem 4. In: Erd\u0151s, P., Katona, G.O.H. (eds.) Proceedings of the Colloquium on Theory of Graphs Held in Tihany, Hungary, 1966, p. 362 (1968)"},{"issue":"2","key":"2_CR19","doi-asserted-by":"crossref","first-page":"P2.37","DOI":"10.37236\/7487","volume":"25","author":"G Golan","year":"2018","unstructured":"Golan, G., Shan, S.: Nonempty intersection of longest paths in $$2K_2$$-free graphs. Electron. J. Comb. 25(2), P2.37 (2018)","journal-title":"Electron. J. Comb."},{"issue":"11","key":"2_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0895-7177(93)90259-2","volume":"17","author":"F Harary","year":"1993","unstructured":"Harary, F., Loukakis, E., Tsouros, C.: The geodetic number of a graph. Math. Comput. Modell. 17(11), 89\u201395 (1993)","journal-title":"Math. Comput. Modell."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2016.02.002","volume":"206","author":"AS Jobson","year":"2016","unstructured":"Jobson, A.S., K\u00e9zdy, A.E., Lehel, J., White, S.C.: Detour trees. Discrete Appl. Math. 206, 73\u201380 (2016). https:\/\/doi.org\/10.1016\/j.dam.2016.02.002","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"2_CR22","doi-asserted-by":"publisher","first-page":"419","DOI":"10.7151\/dmgt.1800","volume":"35","author":"F Joos","year":"2015","unstructured":"Joos, F.: A note on longest paths in circular arc graphs. Discussiones Mathematicae Graph Theory 35(3), 419\u2013426 (2015)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"2_CR23","unstructured":"Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. arXiv:2001.03098 (2020). To appear at IPEC 2020"},{"key":"2_CR24","first-page":"43","volume":"29","author":"S Klav\u017ear","year":"1990","unstructured":"Klav\u017ear, S., Petkov\u0161ek, M.: Graphs with nonempty intersection of longest paths. Ars Combinatoria 29, 43\u201352 (1990)","journal-title":"Ars Combinatoria"},{"issue":"5","key":"2_CR25","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1137\/0221056","volume":"21","author":"MC Loui","year":"1992","unstructured":"Loui, M.C., Luginbuhl, D.R.: Optimal on-line simulations of tree machines by random access machines. SIAM J. Comput. 21(5), 959\u2013971 (1992). https:\/\/doi.org\/10.1137\/0221056","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(96)00078-6","volume":"59","author":"MS Madanlal","year":"1996","unstructured":"Madanlal, M.S., Venkatesan, G., Rangan, C.P.: Tree 3-spanners on interval, permutation and regular bipartite graphs. Inf. Process. Lett. 59(2), 97\u2013102 (1996). https:\/\/doi.org\/10.1016\/0020-0190(96)00078-6","journal-title":"Inf. Process. Lett."},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2018.05.032","volume":"745","author":"M Mezzini","year":"2018","unstructured":"Mezzini, M.: Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. Theoret. Comput. Sci. 745, 63\u201374 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.05.032","journal-title":"Theoret. Comput. Sci."},{"issue":"17","key":"2_CR28","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1016\/j.dam.2010.08.015","volume":"158","author":"BS Panda","year":"2010","unstructured":"Panda, B.S., Das, A.: Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms. Discrete Appl. Math. 158(17), 1913\u20131935 (2010). https:\/\/doi.org\/10.1016\/j.dam.2010.08.015","journal-title":"Discrete Appl. Math."},{"key":"2_CR29","doi-asserted-by":"publisher","unstructured":"Pelayo, I.M.: Geodesic Convexity in Graphs. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-8699-2","DOI":"10.1007\/978-1-4614-8699-2"},{"issue":"1","key":"2_CR30","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1137\/130910658","volume":"28","author":"D Rautenbach","year":"2014","unstructured":"Rautenbach, D., Sereni, J.: Transversals of longest paths and cycles. SIAM J. Discrete Math. 28(1), 335\u2013341 (2014). https:\/\/doi.org\/10.1137\/130910658","journal-title":"SIAM J. Discrete Math."},{"issue":"11","key":"2_CR31","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1016\/j.disc.2013.02.016","volume":"313","author":"SF de Rezende","year":"2013","unstructured":"de Rezende, S.F., Fernandes, C.G., Martin, D.M., Wakabayashi, Y.: Intersecting longest paths. Discrete Math. 313(11), 1401\u20131408 (2013). https:\/\/doi.org\/10.1016\/j.disc.2013.02.016","journal-title":"Discrete Math."},{"issue":"2","key":"2_CR32","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G Venkatesan","year":"1997","unstructured":"Venkatesan, G., Rotics, U., Madanlal, M.S., Makowsky, J.A., Rangan, C.P.: Restrictions of minimum spanner problems. Inf. Comput. 136(2), 143\u2013164 (1997). https:\/\/doi.org\/10.1006\/inco.1997.2641","journal-title":"Inf. Comput."},{"key":"2_CR33","unstructured":"Walther, H., Voss, H.J.: \u00dcber Kreise in Graphen. Deutscher Verlag der Wissenschaften (1974)"},{"issue":"2","key":"2_CR34","doi-asserted-by":"publisher","first-page":"211","DOI":"10.7146\/math.scand.a-11630","volume":"38","author":"T Zamfirescu","year":"1976","unstructured":"Zamfirescu, T.: On longest paths and circuits in graphs. Mathematica Scandinavica 38(2), 211\u2013239 (1976)","journal-title":"Mathematica Scandinavica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T22:04:51Z","timestamp":1620165891000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_2","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":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","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":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","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":"78","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":"27","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":"35% - 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","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":"10","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":"Due to the Corona pandemic the conference 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)"}}]}}