{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T11:31:49Z","timestamp":1786188709957,"version":"3.56.0"},"reference-count":31,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T00:00:00Z","timestamp":1777248000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005005","name":"Ben-Gurion University of the Negev","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0004"],"award-info":[{"award-number":["ANR-21-CE48-0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015723","name":"Universit\u00e9 Clermont-Auvergne","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100015723","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001852","name":"CEFIPRA","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001852","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ANR-16-IDEX-0001"],"award-info":[{"award-number":["ANR-16-IDEX-0001"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.ic.2026.105456","type":"journal-article","created":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:38:08Z","timestamp":1777549088000},"page":"105456","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":1,"special_numbering":"C","title":["Algorithms and complexity for geodetic sets on interval and chordal graphs"],"prefix":"10.1016","volume":"311","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0534-6417","authenticated-orcid":false,"given":"Dibyayan","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7565-8593","authenticated-orcid":false,"given":"Sandip","family":"Das","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8198-693X","authenticated-orcid":false,"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7663-6265","authenticated-orcid":false,"given":"Harmender","family":"Gahlawat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4757-0169","authenticated-orcid":false,"given":"Dimitri","family":"Lajou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2026.105456_bib0001","series-title":"31st International Symposium on Algorithms and Computation (ISAAC 2020)","first-page":"7:1","article-title":"Algorithms and complexity for geodetic sets on planar and chordal graphs","volume":"181","author":"Chakraborty","year":"2020"},{"key":"10.1016\/j.ic.2026.105456_bib0002","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2023.114217","article-title":"Algorithms and complexity for geodetic sets on partial grids","volume":"979","author":"Chakraborty","year":"2023","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"10.1016\/j.ic.2026.105456_bib0003","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0895-7177(93)90259-2","article-title":"The geodetic number of a graph","volume":"17","author":"Harary","year":"1993","journal-title":"Math. Comput. Model."},{"key":"10.1016\/j.ic.2026.105456_bib0004","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-84128-6","article-title":"Introduction to Graph Convexity: An Algorithmic Approach","author":"Ara\u00fajo","year":"2025"},{"issue":"3","key":"10.1016\/j.ic.2026.105456_bib0005","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/0607049","article-title":"Convexity in graphs and hypergraphs","volume":"7","author":"Farber","year":"1986","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"10.1016\/j.ic.2026.105456_bib0006","series-title":"Geodesic Convexity in Graphs","author":"Pelayo","year":"2013"},{"key":"10.1016\/j.ic.2026.105456_bib0007","series-title":"Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020)","first-page":"102","article-title":"Hardness and approximation for the geodetic set problem in some graph classes","volume":"12016","author":"Chakraborty","year":"2020"},{"issue":"4","key":"10.1016\/j.ic.2026.105456_bib0008","doi-asserted-by":"crossref","first-page":"2307","DOI":"10.1109\/TMC.2021.3119421","article-title":"Optimizing cross-Line dispatching for minimum electric bus fleet","volume":"22","author":"Wang","year":"2023","journal-title":"IEEE Trans. Mob. Comput."},{"key":"10.1016\/j.ic.2026.105456_bib0009","series-title":"Proceedings of the 10Th Latin American Symposium on Theoretical Informatics (LATIN\u201912)","first-page":"279","article-title":"Computing minimum geodetic sets of proper interval graphs","volume":"7256","author":"Ekim","year":"2012"},{"key":"10.1016\/j.ic.2026.105456_bib0010","first-page":"67","article-title":"Computing geodetic bases of chordal and split graph","volume":"22","author":"Douthat","year":"1996","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"10.1016\/j.ic.2026.105456_bib0011","series-title":"Proceedings of the International Conference on Discrete Mathematics (ICDM)","first-page":"101","article-title":"On the complexity of the geodetic and convexity numbers of a graph","volume":"7","author":"Dourado","year":"2008"},{"issue":"4","key":"10.1016\/j.ic.2026.105456_bib0012","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1016\/j.disc.2009.09.018","article-title":"Some remarks on the geodetic number of a graph","volume":"310","author":"Dourado","year":"2010","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2026.105456_bib0013","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.ipl.2018.02.012","article-title":"On the hardness of finding the geodetic number of a subcubic graph","volume":"135","author":"Bueno","year":"2018","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"10.1016\/j.ic.2026.105456_bib0014","doi-asserted-by":"crossref","DOI":"10.1016\/j.disc.2022.112985","article-title":"Well-partitioned chordal graphs","volume":"345","author":"Ahn","year":"2022","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/j.ic.2026.105456_bib0015","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/15M1013389","article-title":"Polynomial time algorithms for computing a minimum hull set in distance-Hereditary and chordal graphs","volume":"30","author":"Kant\u00e9","year":"2016","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.ic.2026.105456_bib0016","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.tcs.2018.05.032","article-title":"Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs","volume":"745","author":"Mezzini","year":"2018","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.ic.2026.105456_bib0017","first-page":"401","article-title":"Parameterized complexity of geodetic set","volume":"26","author":"Kellerhals","year":"2022","journal-title":"J. Graph Algo. Appl."},{"key":"10.1016\/j.ic.2026.105456_bib0018","series-title":"20th International Symposium on Parameterized and Exact Computation, IPEC 2025, Warsaw, Poland, September 17\u201319, 2025","first-page":"28:1","article-title":"Geodetic set on graphs of constant pathwidth and feedback vertex set number","volume":"358","author":"Tale","year":"2025"},{"key":"10.1016\/j.ic.2026.105456_bib0019","series-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)","article-title":"Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover","author":"Foucaud","year":"2024"},{"key":"10.1016\/j.ic.2026.105456_bib0020","series-title":"Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24\u201326, 2021, Proceedings 27","first-page":"76","article-title":"On the approximation hardness of geodetic set and its variants","author":"Davot","year":"2021"},{"key":"10.1016\/j.ic.2026.105456_bib0021","series-title":"42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)","first-page":"33:1","article-title":"Metric dimension and geodetic set parameterized by vertex cover","volume":"327","author":"Foucaud","year":"2025"},{"key":"10.1016\/j.ic.2026.105456_bib0022","series-title":"Structure and properties of maximal outerplanar graphs","author":"Allgeier","year":"2009"},{"key":"10.1016\/j.ic.2026.105456_bib0023","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1007\/s00453-016-0184-1","article-title":"Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity","volume":"78","author":"Foucaud","year":"2017","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2026.105456_bib0024","doi-asserted-by":"crossref","DOI":"10.23638\/DMTCS-21-1-8","article-title":"Parameterized complexity of equitable coloring","volume":"vol. 21 no. 1, ICGT 2018","author":"Gomes","year":"2019","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"10.1016\/j.ic.2026.105456_bib0025","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.tcs.2014.10.002","article-title":"Induced subgraph isomorphism on proper interval and bipartite permutation graphs","volume":"562","author":"Heggernes","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.ic.2026.105456_bib0026","first-page":"501","article-title":"Detecting fixed patterns in chordal graphs in polynomial time","volume":"69","author":"Belmonte","year":"2014","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2026.105456_bib0027","series-title":"Treewidth, Computations and Approximations","author":"Kloks","year":"1994"},{"issue":"7","key":"10.1016\/j.ic.2026.105456_bib0028","doi-asserted-by":"crossref","first-page":"3047","DOI":"10.1007\/s00453-019-00568-7","article-title":"Optimality programme in segment and string graphs","volume":"81","author":"Bonnet","year":"2019","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2026.105456_bib0029","series-title":"33rd International Symposium on Algorithms and Computation (ISAAC 2022)","first-page":"12:1","article-title":"Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond","volume":"248","author":"Chakraborty","year":"2022"},{"issue":"5","key":"10.1016\/j.ic.2026.105456_bib0030","doi-asserted-by":"crossref","first-page":"3755","DOI":"10.1051\/ro\/2024120","article-title":"On the computational complexity of the strong geodetic recognition problem","volume":"58","author":"Lima","year":"2024","journal-title":"RAIRO Oper. Res."},{"issue":"1\u20133","key":"10.1016\/j.ic.2026.105456_bib0031","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.disc.2004.08.039","article-title":"On the Steiner, geodetic and hull numbers of graphs","volume":"293","author":"Hernando","year":"2005","journal-title":"Discrete Math."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000532?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000532?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T22:25:56Z","timestamp":1783376756000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000532"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":31,"alternative-id":["S0890540126000532"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105456","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Algorithms and complexity for geodetic sets on interval and chordal graphs","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105456","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier Inc.","name":"copyright","label":"Copyright"}],"article-number":"105456"}}