{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T21:41:34Z","timestamp":1780436494724,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"\n Let (\n G<\/jats:italic>\n = (\n V(G)<\/jats:italic>\n ,\n E(G)<\/jats:italic>\n )) be a directed graph with nonnegative edge lengths and let\n P<\/jats:italic>\n be a shortest path from\n s<\/jats:italic>\n to\n t<\/jats:italic>\n in\n G<\/jats:italic>\n . In the\n replacement paths<\/jats:italic>\n problem we are required to compute for every edge\n e<\/jats:italic>\n in\n P<\/jats:italic>\n , the length of a shortest path from\n s<\/jats:italic>\n to\n t<\/jats:italic>\n that avoids\n e<\/jats:italic>\n . The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in\n P<\/jats:italic>\n is removed from the graph in its turn and the distance from\n s<\/jats:italic>\n to\n t<\/jats:italic>\n in the modified graph is computed. The running time of this algorithm is\n O<\/jats:italic>\n (\n m n<\/jats:italic>\n +\n n<\/jats:italic>\n 2<\/jats:sup>\n log\n n<\/jats:italic>\n ), where\n n<\/jats:italic>\n = |\n V(G)<\/jats:italic>\n | and\n m<\/jats:italic>\n = |\n E(G)<\/jats:italic>\n |.\n <\/jats:p>\n \n The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the\n k simple shortest paths<\/jats:italic>\n from\n s<\/jats:italic>\n to\n t<\/jats:italic>\n in directed graphs [Yen 1971; Lawler 1972] repeatedly computes the replacement paths from\n s<\/jats:italic>\n to\n t<\/jats:italic>\n . Its running time is\n O<\/jats:italic>\n (\n kn<\/jats:italic>\n (\n m<\/jats:italic>\n +\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )). Second, the computation of\n Vickrey pricing<\/jats:italic>\n of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [2001] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph.\n <\/jats:p>\n \n In this article we present a near-linear time algorithm for computing replacement paths in weighted\n planar<\/jats:italic>\n directed graphs. In particular, the algorithm computes the lengths of the replacement paths in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n 3<\/jats:sup>\n n<\/jats:italic>\n ) time (recall that in planar graphs\n m<\/jats:italic>\n =\n O<\/jats:italic>\n (\n n<\/jats:italic>\n )). This result immediately improves the running time of the two applications mentioned before by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [2005] that supports multisource shortest paths queries in planar directed graphs in logarithmic time.\n <\/jats:p>\n \n Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time \u00d5 (\n h<\/jats:italic>\n ), where\n h<\/jats:italic>\n is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.\n <\/jats:p>","DOI":"10.1145\/1824777.1824784","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A near-linear-time algorithm for computing replacement paths in planar directed graphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[{"name":"Microsoft Israel R&D Center, Herzlia, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[{"name":"Bar Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10546"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 34--43","author":"Bernstein A.","unstructured":"Bernstein , A. and Karger , D . 2008. Improved distance sensitivity oracles via random sampling . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 34--43 . Bernstein, A. and Karger, D. 2008. Improved distance sensitivity oracles via random sampling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 34--43."},{"key":"e_1_2_1_3_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 2009. Introduction to Algorithms 3rd Ed. The MIT Press. Cormen T. Leiserson C. and Rivest R. 2009. Introduction to Algorithms 3rd Ed. The MIT Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62254"},{"key":"e_1_2_1_5_1","unstructured":"Demetrescu C. Thorup M. Chaudhury R. A. and Ramachandran V. Oracles for distances avoiding a link-failure. http:\/\/scitation.aip.org\/getabs\/servlet\/GetabsServlet?prog-normalGrid=SMJ@AT00003700000500129000001@idtype=cvips@gifs=yes Demetrescu C. Thorup M. Chaudhury R. A. and Ramachandran V. Oracles for distances avoiding a link-failure. http:\/\/scitation.aip.org\/getabs\/servlet\/GetabsServlet?prog-normalGrid=SMJ@AT00003700000500129000001@idtype=cvips@gifs=yes"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 232--241","author":"Fakcharoenphol J.","unstructured":"Fakcharoenphol , J. and Rao , S . 2001. Planar graphs, negative weight edges, shortest paths, near linear time . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 232--241 . Fakcharoenphol, J. and Rao, S. 2001. Planar graphs, negative weight edges, shortest paths, near linear time. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 232--241."},{"key":"e_1_2_1_9_1","first-page":"229","article-title":"On straight-line representation of planar graphs. Acta Sci","volume":"11","author":"F\u00e1ry I.","year":"1948","unstructured":"F\u00e1ry , I. 1948 . On straight-line representation of planar graphs. Acta Sci . Math. (Szeged) 11 , 229 -- 233 . F\u00e1ry, I. 1948. On straight-line representation of planar graphs. Acta Sci. Math. (Szeged) 11, 229--233.","journal-title":"Math. (Szeged)"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (42nd) (FOCS). 252--259","author":"Hershberger J.","unstructured":"Hershberger , J. and Suri , S . 2001. Vickrey prices and shortest paths: what is an edge worth . In Proceedings of the IEEE Symposium on Foundations of Computer Science (42nd) (FOCS). 252--259 . Hershberger, J. and Suri, S. 2001. Vickrey prices and shortest paths: what is an edge worth. In Proceedings of the IEEE Symposium on Foundations of Computer Science (42nd) (FOCS). 252--259."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 343--354","author":"Hershberger J.","unstructured":"Hershberger , J. , Suri , S. , and Bhosle , A . 2003. On the difficulty of some shortest path problems . In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 343--354 . Hershberger, J., Suri, S., and Bhosle, A. 2003. On the difficulty of some shortest path problems. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 343--354."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222071"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 146--155","author":"Klein P.","year":"2005","unstructured":"Klein , P. 2005 . Multiple-Source shortest paths in planar graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 146--155 . Klein, P. 2005. Multiple-Source shortest paths in planar graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 146--155."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 236--245","author":"Klein P.","unstructured":"Klein , P. , Mozes , S. , and Weimann , O . 2009. Shortest paths in directed planar graphs with negative lengths: A linear-space o(n log2 n)-time algorithm . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 236--245 . Klein, P., Mozes, S., and Weimann, O. 2009. Shortest paths in directed planar graphs with negative lengths: A linear-space o(n log2 n)-time algorithm. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 236--245."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00175-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Roditty L.","year":"2007","unstructured":"Roditty , L. 2007 . On the k-simple shortest paths in weighted directed graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). Roditty, L. 2007. On the k-simple shortest paths in weighted directed graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_21"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824784"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824784","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}