{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:34:58Z","timestamp":1725744898422},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_1","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"1-12","source":"Crossref","is-referenced-by-count":2,"title":["The Online Replacement Path Problem"],"prefix":"10.1007","author":[{"given":"David","family":"Adjiashvili","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpaolo","family":"Oriolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Senatore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"8","key":"1_CR1","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/j.dam.2010.12.018","volume":"159","author":"D. Adjiashvili","year":"2011","unstructured":"Adjiashvili, D., Zenklusen, R.: An s - t connection problem with adaptability. Discrete Applied Mathematics\u00a0159(8), 695\u2013705 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1007\/11561071_76","volume-title":"Algorithms \u2013 ESA 2005","author":"H. Aissi","year":"2005","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation complexity of min-max (Regret) versions of shortest path, spanning tree, and knapsack. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 862\u2013873. Springer, Heidelberg (2005)"},{"issue":"3","key":"1_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1002\/net.3230180306","volume":"18","author":"G. Andreatta","year":"1988","unstructured":"Andreatta, G., Romeo, L.: Stochastic shortest paths with recourse. Networks\u00a018(3), 193\u2013204 (1988)","journal-title":"Networks"},{"key":"1_CR4","unstructured":"Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes. Technical report, Univ. of Maryland Institute for Advanced Computer Studies Report No. UMIACS-TR-95-96, College Park, MD, USA (1995)"},{"key":"1_CR5","first-page":"261","volume-title":"SODA 1991","author":"A. Bar-Noy","year":"1991","unstructured":"Bar-Noy, A., Schieber, B.: The canadian traveller problem. In: SODA 1991, pp. 261\u2013270. SIAM, Philadelphia (1991)"},{"key":"1_CR6","first-page":"742","volume-title":"SODA 2010","author":"A. Bernstein","year":"2010","unstructured":"Bernstein, A.: A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In: SODA 2010, pp. 742\u2013755. SIAM, Philadelphia (2010)"},{"key":"1_CR7","first-page":"367","volume-title":"FOCS 2005","author":"K. Dhamdhere","year":"2005","unstructured":"Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: Approximation algorithms for demand-robust covering problems. In: FOCS 2005, pp. 367\u2013378. IEEE Computer Society, Washington, DC (2005)"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1824777.1824784","volume":"6","author":"Y. Emek","year":"2010","unstructured":"Emek, Y., Peleg, D., Roditty, L.: A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Trans. Algorithms\u00a06, 64:1\u201364:13 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM\u00a034, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.ipl.2008.12.015","volume":"109","author":"Z. Gotthilf","year":"2009","unstructured":"Gotthilf, Z., Lewenstein, M.: Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett.\u00a0109, 352\u2013355 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R. Hassin","year":"1992","unstructured":"Hassin, R.: Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research\u00a017(1), 36\u201342 (1992)","journal-title":"Mathematics of Operations Research"},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1721837.1721846","volume":"6","author":"P.N. Klein","year":"2010","unstructured":"Klein, P.N., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2\n                n)-time algorithm. ACM Trans. Algorithms\u00a06, 30:1\u201330:18 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"1_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","volume":"8","author":"K. Malik","year":"1989","unstructured":"Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Operations Research Letters\u00a08(4), 223\u2013227 (1989)","journal-title":"Operations Research Letters"},{"key":"1_CR14","unstructured":"Moreno, A., Valls, A., Ribes, A.: Finding efficient organ transport routes using multi-agent systems. In: Proceedings of the IEEE 3rd International Workshop on Enterprise Networking and Computing in Health Care Industry (Healthcom), pp. 233\u2013258 (2001)"},{"issue":"1","key":"1_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(98)00077-5","volume":"67","author":"E. Nardelli","year":"1998","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Finding the detour-critical edge of a shortest path between two nodes. Information Processing Letters\u00a067(1), 51\u201354 (1998)","journal-title":"Information Processing Letters"},{"key":"1_CR16","first-page":"2003","volume":"35","author":"E. Nardelli","year":"1999","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica\u00a035, 2003 (1999)","journal-title":"Algorithmica"},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(00)00175-7","volume":"79","author":"E. Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Information Processing Letters\u00a079(2), 81\u201385 (2001)","journal-title":"Information Processing Letters"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-44679-6_31","volume-title":"Computing and Combinatorics","author":"E. Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 278\u2013287. Springer, Heidelberg (2001)"},{"key":"1_CR19","unstructured":"Nikolova, E., Karger, D.R.: Route planning under uncertainty: the canadian traveller problem. In: AAAI 2008, pp. 969\u2013974. AAAI Press (2008)"},{"key":"1_CR20","first-page":"129","volume-title":"STOC 1999","author":"N. Nisan","year":"1999","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: STOC 1999, pp. 129\u2013140. ACM, New York (1999)"},{"key":"1_CR21","series-title":"LNCS","first-page":"610","volume-title":"ICALP 1989","author":"C.H. Papadimitriou","year":"1989","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) ICALP 1989. LNCS, vol.\u00a0372, pp. 610\u2013620. Springer, Heidelberg (1989)"},{"key":"1_CR22","first-page":"920","volume-title":"SODA 2007","author":"L. Roditty","year":"2007","unstructured":"Roditty, L.: On the k-simple shortest paths problem in weighted directed graphs. In: SODA 2007, pp. 920\u2013928. SIAM, Philadelphia (2007)"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/11523468_21","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 249\u2013260. Springer, Heidelberg (2005)"},{"issue":"2","key":"1_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM\u00a022(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: Faster replacement paths. In: SODA 2011, pp. 1337\u20131346. SIAM (2011)","DOI":"10.1137\/1.9781611973082.102"},{"key":"1_CR26","first-page":"756","volume-title":"SODA 2010","author":"C. Wulff-Nilsen","year":"2010","unstructured":"Wulff-Nilsen, C.: Solving the replacement paths problem for planar directed graphs in O(n logn) time. In: SODA 2010, pp. 756\u2013765. SIAM, Philadelphia (2010)"},{"issue":"6","key":"1_CR27","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/S0305-0548(97)00085-3","volume":"25","author":"G. Yu","year":"1998","unstructured":"Yu, G., Yang, J.: On the robust shortest path problem. Computers & Operations Research\u00a025(6), 457\u2013468 (1998)","journal-title":"Computers & Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:00:22Z","timestamp":1558011622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}