{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:58:24Z","timestamp":1772297904399,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2004,6,7]],"date-time":"2004-06-07T00:00:00Z","timestamp":1086566400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2005,3]]},"DOI":"10.1007\/s10107-004-0517-8","type":"journal-article","created":{"date-parts":[[2004,6,5]],"date-time":"2004-06-05T05:05:39Z","timestamp":1086411939000},"page":"355-369","source":"Crossref","is-referenced-by-count":32,"title":["Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs"],"prefix":"10.1007","volume":"102","author":[{"given":"Ramkumar","family":"Ramaswamy","sequence":"first","affiliation":[]},{"given":"James B.","family":"Orlin","sequence":"additional","affiliation":[]},{"given":"Nilopal","family":"Chakravarti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,6,7]]},"reference":[{"key":"CR1","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ, 1993"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1006\/jpdc.1997.1383","volume":"46","author":"Banerjee","year":"1997","unstructured":"Banerjee, S., Saxena, S.: Parallel algorithm for finding the most vital edge in weighted graphs. J. Parallel Dist. Comput. 46, 101?104 (1997)","journal-title":"J. Parallel Dist. Comput."},{"key":"CR3","unstructured":"Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital edges and nodes. Technical Report CS-TR-3539, University of Maryland Institute for Advanced Studies, College Park, 1995"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01187017","volume":"11","author":"Booth","year":"1994","unstructured":"Booth, H., Westbrook, J.: A linear algorithm for analysis of minimum spanning and shortest path trees of planar graphs. Algorithmica 11, 341?352 (1994)","journal-title":"Algorithmica"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248?264 (1972)","journal-title":"J. ACM"},{"key":"CR6","first-page":"338","volume":"25","author":"Fredman","year":"1984","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Proceedings of the 25th Annual IEEE Symposium on the Foundation of Computer Science, 338?446 (1984). Full paper in Journal of the ACM 34, 596?615 (1984)","journal-title":"Proceedings of the"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Galil, Z., Spencer, T.H.: Efficient implementations of graph algorithms using contraction. Proceedings of the 25th Annual Symposium on the Foundations of Computer Science (FOCS ?84), 1984, pp. 347?357","DOI":"10.1109\/SFCS.1984.715935"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Gal, T.: Sensitivity Analysis, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy. W. deGruyter, Berlin and New York, 1995","DOI":"10.1515\/9783110871203"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Gal, T., Greenberg, H.J., (eds.): Advances in Sensitivity Analysis and Parametric Programming. Vol. 6 of International Series in Operations Research and Management Science, Kluwer Academic Publishers, Boston, 1997","DOI":"10.1007\/978-1-4615-6103-3"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Greenberg H.J.: An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization. In: D. Woodruff (ed.), Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, 1998, pp. 97?148","DOI":"10.1007\/978-1-4757-2807-1_4"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S.: Vickrey prices and shortest paths: What is an edge worth? In: Proc. 42nd Annu. IEEE Symp. Found. Comput. Sci., 2001, pp. 252?259","DOI":"10.1109\/SFCS.2001.959899"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S.: Erratum to ??Vickrey prices and shortest paths: What is an edge worth??? Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science (FOCS?02), 2002, pp. 809?810","DOI":"10.1109\/SFCS.2002.1182006"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S., Bhosle, A.: On the difficulty of some shortest path problems. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2003), 2003, pp. 343?354","DOI":"10.1007\/3-540-36494-3_31"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(91)90028-G","volume":"39","author":"Hsu","year":"1991","unstructured":"Hsu, L.H., Jan, R.H., Lee, Y.C., Hung, C.N., Chern, M.S.: Finding the most vital edge with respect to minimum spanning tree in weighted graphs. Inf. Proc. Lett. 39, 277?281 (1991)","journal-title":"Inf. Proc. Lett."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1016\/0167-8191(92)90061-B","volume":"18","author":"Hsu","year":"1992","unstructured":"Hsu, L.H., Wang, P.F., Wu, C.T.: Parallel algorithms for finding the most vital edge with respect to minimum spanning tree. Parallel Comput. 18, 1143?1155 (1992)","journal-title":"Parallel Comput."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 321?328 (1995)","journal-title":"J. ACM"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","volume":"8","author":"Malik","year":"1989","unstructured":"Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital edges in the shortest path problem. Operations Research Letters 8, 223?227 (1989)","journal-title":"Operations Research Letters"},{"key":"CR18","unstructured":"Ramaswamy, R.: Sensitivity Analysis in Combinatorial Optimization. Unpublished Fellow Programme dissertation, Indian Institute of Management Calcutta, India, 1994"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.3230100402","volume":"10","author":"Shier","year":"1980","unstructured":"Shier, D.R., Witzgall, C.: Edge tolerances in shortest path and network flow problems. Networks 10, 277 (1980)","journal-title":"Networks"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"Shigeno, M., Uno, T.: Personal Correspondence, 2002","DOI":"10.3757\/jser.61.97"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Inf. Proc. Lett. 14, 30?33 (1982)","journal-title":"Inf. Proc. Lett."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0167-6377(84)90076-2","volume":"2","author":"Tarjan","year":"1984","unstructured":"Tarjan, R.E.: A simple version of Karzanov?s blocking flow algorithm. Oper. Res. Lett. 2, 265?268 (1984)","journal-title":"Oper. Res. Lett."},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Undirected Single Source Shortest Paths in Linear Time. Proceedings of the 38th Annual Symposium on the Foundations of Computer Science (FOCS ?97), 1997","DOI":"10.1109\/SFCS.1997.646088"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/S0020-0190(96)00172-X","volume":"60","author":"Venema","year":"1996","unstructured":"Venema, S., Shen, H., Suraweera, F.: NC Algorithms for the Single Most Vital Edge Problem with Respect to Shortest Paths. Inf. Proc. Lett. 60, 243?248 (1996)","journal-title":"Inf. Proc. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0517-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-004-0517-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0517-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,2]],"date-time":"2020-04-02T10:13:54Z","timestamp":1585822434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-004-0517-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,7]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["517"],"URL":"https:\/\/doi.org\/10.1007\/s10107-004-0517-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6,7]]}}}