{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:10:36Z","timestamp":1767856236392,"version":"3.49.0"},"reference-count":14,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3827,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1016\/s0304-3975(02)00438-3","type":"journal-article","created":{"date-parts":[[2003,2,12]],"date-time":"2003-02-12T12:35:20Z","timestamp":1045053320000},"page":"167-177","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":70,"title":["Finding the most vital node of a shortest path"],"prefix":"10.1016","volume":"296","author":[{"given":"Enrico","family":"Nardelli","sequence":"first","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00438-3_BIB1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0167-6377(89)90003-5","article-title":"Finding the most vital arcs in a network","volume":"8","author":"Ball","year":"1989","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0304-3975(02)00438-3_BIB2","unstructured":"A. Bar-Noy, S. Khuller, B. Schieber, The complexity of finding most vital arcs and nodes, TR CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995."},{"key":"10.1016\/S0304-3975(02)00438-3_BIB3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0167-6377(82)90020-7","article-title":"Most vital links and nodes in weighted networks","volume":"1","author":"Corley","year":"1982","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0304-3975(02)00438-3_BIB4","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connection with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"issue":"3","key":"10.1016\/S0304-3975(02)00438-3_BIB5","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB6","doi-asserted-by":"crossref","unstructured":"J. Hershberger, S. Suri, Vickrey prices and shortest paths: what is an edge worth? Proc. 42nd Annu. IEEE Symp. on Foundations of Computer Science (FOCS\u201901), 2001, pp. 252\u2013260.","DOI":"10.1109\/SFCS.2001.959899"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB7","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","article-title":"The k most vital arcs in the shortest path problem","volume":"8","author":"Malik","year":"1989","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10.1016\/S0304-3975(02)00438-3_BIB8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0020-0190(98)00077-5","article-title":"Finding the detour-critical edge of a shortest path between two nodes","volume":"67","author":"Nardelli","year":"1998","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"10.1016\/S0304-3975(02)00438-3_BIB9","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(00)00175-7","article-title":"A faster computation of the most vital edge of a shortest path between two nodes","volume":"79","author":"Nardelli","year":"2001","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(02)00438-3_BIB10","first-page":"1","volume":"vol. 1563","author":"Nisan","year":"1999"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB11","doi-asserted-by":"crossref","unstructured":"N. Nisan, A. Ronen, Algorithmic mechanism design, Proc. 31st Annu. ACM Symp. on Theory of Computing (STOC\u201999), 1999, pp. 129\u2013140.","DOI":"10.1145\/301250.301287"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB12","series-title":"Rules of Encounter","author":"Rosenschein","year":"1994"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB13","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00438-3_BIB14","unstructured":"S. Venema, H. Shen, F. Suraweera, A parallel algorithm for the single most vital vertex problem with respect to single source shortest paths, Online Proc. First Internat. Conf. on Parallel and Distributed Computing, Applications and Technologies (PDCAT\u20192000), Chapter 22, http:\/\/www2.comp.polyu.edu.hk\/PDCAT2000\/publish.html."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502004383?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502004383?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T00:52:25Z","timestamp":1759625545000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397502004383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["S0304397502004383"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00438-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,3]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Finding the most vital node of a shortest path","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0304-3975(02)00438-3","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2002 Elsevier Science B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}