{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T14:17:13Z","timestamp":1783174633217,"version":"3.54.6"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T00:00:00Z","timestamp":1788220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"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\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009935","name":"Indo-French Centre for Applied Mathematics","doi-asserted-by":"publisher","award":["MA\/IFCAM\/18\/39"],"award-info":[{"award-number":["MA\/IFCAM\/18\/39"]}],"id":[{"id":"10.13039\/100009935","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,9]]},"DOI":"10.1016\/j.ic.2026.105460","type":"journal-article","created":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T15:16:05Z","timestamp":1779203765000},"page":"105460","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Algorithms and complexity for monitoring edge-geodetic sets in graphs"],"prefix":"10.1016","volume":"312","author":[{"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Clara","family":"Marcille","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.B.","family":"Sandeep","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sagnik","family":"Sen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3324-7037","authenticated-orcid":false,"given":"S","family":"Taruni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2026.105460_bib0001","series-title":"Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9\u201311, 2023, Proceedings","first-page":"245","article-title":"Monitoring edge-geodetic sets in graphs","author":"Foucaud","year":"2023"},{"issue":"7","key":"10.1016\/j.ic.2026.105460_bib0002","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1080\/0020716031000103376","article-title":"On the edge geodetic number of a graph","volume":"80","author":"Atici","year":"2003","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"10.1016\/j.ic.2026.105460_bib0003","first-page":"1","article-title":"On the geodetic number of a graph","volume":"39","author":"Chartrand","year":"2002","journal-title":"Netw. Int. J."},{"key":"10.1016\/j.ic.2026.105460_bib0004","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/j.dam.2021.07.002","article-title":"Monitoring the edges of a graph using distances","volume":"319","author":"Foucaud","year":"2022","journal-title":"Discrete Appl. Math."},{"issue":"11","key":"10.1016\/j.ic.2026.105460_bib0005","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."},{"issue":"3","key":"10.1016\/j.ic.2026.105460_bib0006","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s00373-018-1885-9","article-title":"Strong geodetic number of complete bipartite graphs and of graphs with specified diameter","volume":"34","author":"Ir\u0161i\u010d","year":"2018","journal-title":"Graphs Comb."},{"issue":"3","key":"10.1016\/j.ic.2026.105460_bib0007","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1080\/09720529.2007.10698129","article-title":"Edge geodetic number of a graph","volume":"10","author":"Santhakumaran","year":"2007","journal-title":"J. Discrete Math. Sci. Cryptogr."},{"issue":"2","key":"10.1016\/j.ic.2026.105460_bib0008","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","article-title":"Edge-deletion problems","volume":"10","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ic.2026.105460_bib0009","unstructured":"S.R. Dev, S. Dey, F. Foucaud, N. Krishna, L.R. Sulochana, Monitoring edge-geodetic sets in graphs, 2023arXiv: 2210.03774."},{"key":"10.1016\/j.ic.2026.105460_bib0010","article-title":"Monitoring edge-geodetic numbers of Mycielskian graph classes","author":"Li","year":"2024","journal-title":"J. Interconnect. Netw."},{"key":"10.1016\/j.ic.2026.105460_bib0011","article-title":"On the monitoring-edge-geodetic numbers of line graphs","author":"Bao","year":"2023","journal-title":"J. Interconnect. Netw."},{"key":"10.1016\/j.ic.2026.105460_bib0012","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.dam.2023.06.033","article-title":"Monitoring edge-geodetic sets: hardness and graph products","volume":"340","author":"Haslegrave","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2026.105460_bib0013","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1080\/17445760.2024.2301929","article-title":"Monitoring-edge-geodetic sets in product networks","volume":"39","author":"Xu","year":"2024","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"10.1016\/j.ic.2026.105460_bib0014","doi-asserted-by":"crossref","unstructured":"F. Foucaud, C. Marcille, Z.M. Myint, R.B. Sandeep, S. Sagnik, S. Taruni, Bounds and extremal graphs for monitoring edge-geodetic sets in graphs, (2024) arXiv: 2403.09122.","DOI":"10.2139\/ssrn.5311874"},{"key":"10.1016\/j.ic.2026.105460_bib0015","series-title":"Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18\u201321, 2023, Proceedings","first-page":"132","article-title":"Distance-based covering problems for graphs of given cyclomatic number","volume":"vol. 14292","author":"Chakraborty","year":"2023"},{"key":"10.1016\/j.ic.2026.105460_bib0016","unstructured":"G. Colli, Monitoring graph edges via shortest paths: computational complexity and approximation algorithms, Bachelor\u2019s thesis, University of L\u2019Aquila, 2023. arXiv: 2506.12021, https:\/\/hdl.handle.net\/20.500.12319\/14489."},{"key":"10.1016\/j.ic.2026.105460_bib0017","series-title":"Proceedings of the 25th Italian Conference on Theoretical Computer Science, Torino, Italy","first-page":"219","article-title":"On the inapproximability of finding minimum monitoring edge-geodetic sets (short paper)","volume":"vol. 3811","author":"Bil\u00f2","year":"2024"},{"key":"10.1016\/j.ic.2026.105460_bib0018","series-title":"36th International Symposium on Algorithms and Computation (ISAAC 2025)","first-page":"14:1","article-title":"On the (in)approximability of the monitoring edge geodetic set problem","volume":"vol. 359","author":"Bil\u00f2","year":"2025"},{"key":"10.1016\/j.ic.2026.105460_bib0019","series-title":"Algorithms and Discrete Applied Mathematics - 10th International Conference, CALDAM 2024, Bhilai, India, February 15\u201317, 2024, Proceedings","first-page":"29","article-title":"Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity","volume":"vol. 14508","author":"Foucaud","year":"2024"},{"key":"10.1016\/j.ic.2026.105460_bib0020","series-title":"Graph-Theoretic Concepts in Computer Science: 18th International Workshop, WG\u201992 Wiesbaden-Naurod, Germany, June 18\u201320, 1992 Proceedings 18","first-page":"11","article-title":"A simple test for interval graphs","author":"Hsu","year":"1993"},{"key":"10.1016\/j.ic.2026.105460_bib0021","series-title":"Parameterized Algorithms","author":"Cygan","year":"2015"},{"issue":"4","key":"10.1016\/j.ic.2026.105460_bib0022","doi-asserted-by":"crossref","first-page":"401","DOI":"10.7155\/jgaa.00601","article-title":"Parameterized complexity of geodetic set","volume":"26","author":"Kellerhals","year":"2022","journal-title":"J. Graph Algorithms Appl."},{"key":"10.1016\/j.ic.2026.105460_bib0023","series-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","volume":"vol. 138","author":"Courcelle","year":"2012"},{"issue":"1","key":"10.1016\/j.ic.2026.105460_bib0024","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inf. Comput."},{"issue":"2","key":"10.1016\/j.ic.2026.105460_bib0025","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.ic.2026.105460_bib0026","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2022.03.021","article-title":"Exploring the gap between treedepth and vertex cover through vertex integrity","volume":"918","author":"Gima","year":"2022","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.ic.2026.105460_bib0027","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539701385351","article-title":"On the relationship between clique-width and treewidth","volume":"34","author":"Corneil","year":"2005","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.ic.2026.105460_bib0028","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.105460_bib0029","series-title":"Graph Theory and Sparse Matrix Computations","first-page":"1","article-title":"An introduction to chordal graphs and clique trees","volume":"vol. 56","author":"Blair","year":"1993"},{"key":"10.1016\/j.ic.2026.105460_bib0030","series-title":"Treewidth: Computations and Cpproximations","author":"Kloks","year":"1994"},{"issue":"1","key":"10.1016\/j.ic.2026.105460_bib0031","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1006\/jctb.2000.2026","article-title":"Face covers and the genus problem for apex graphs","volume":"82","author":"Mohar","year":"2001","journal-title":"J. Comb. Theory B"},{"issue":"3","key":"10.1016\/j.ic.2026.105460_bib0032","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1002\/jgt.3190200313","article-title":"An induced subgraph characterization of domination perfect graphs","volume":"20","author":"Zvervich","year":"1995","journal-title":"J. Graph Theory"},{"issue":"4","key":"10.1016\/j.ic.2026.105460_bib0033","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.ic.2026.105460_bib0034","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"1-2","key":"10.1016\/j.ic.2026.105460_bib0035","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","article-title":"Some APX-completeness results for cubic graphs","volume":"237","author":"Alimonti","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.ic.2026.105460_bib0036","series-title":"Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24\u201327, 1997","first-page":"262","article-title":"A short guide to approximation preserving reductions","author":"Crescenzi","year":"1997"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S089054012600057X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S089054012600057X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T13:31:08Z","timestamp":1783171868000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S089054012600057X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":36,"alternative-id":["S089054012600057X"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105460","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Algorithms and complexity for monitoring edge-geodetic sets in graphs","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105460","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Published by Elsevier Inc.","name":"copyright","label":"Copyright"}],"article-number":"105460"}}