{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T04:31:33Z","timestamp":1781757093693,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"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":[[2013,3]]},"abstract":"<jats:p>\n            A\n            <jats:italic>distance sensitivity oracle<\/jats:italic>\n            of an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) is a data structure that can report shortest paths when edges of the graph fail. A query (\n            <jats:italic>u<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            ) to this oracle returns a shortest\n            <jats:italic>u<\/jats:italic>\n            -to-\n            <jats:italic>v<\/jats:italic>\n            path in the graph\n            <jats:italic>G<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            \u2216\n            <jats:italic>S<\/jats:italic>\n            ). We present randomized (Monte Carlo) algorithms for constructing a distance sensitivity oracle of size\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\u2212\u03b1<\/jats:sup>\n            ) for |\n            <jats:italic>S<\/jats:italic>\n            | =\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:italic>n<\/jats:italic>\n            \/lg lg\n            <jats:italic>n<\/jats:italic>\n            ) and any choice of 0 &lt;\n            <jats:italic>\u03b1<\/jats:italic>\n            &lt; 1. For real edge-lengths, the oracle is constructed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\u2212\u03b1<\/jats:sup>\n            ) time and a query to this oracle takes\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\u22122(1\u2212\u03b1)\/|S|<\/jats:sup>\n            ) time. For integral edge-lengths in {\u2212\n            <jats:italic>M<\/jats:italic>\n            ,...,\n            <jats:italic>M<\/jats:italic>\n            }, using the current\n            <jats:italic>\u03c9<\/jats:italic>\n            &lt; 2.376 matrix multiplication exponent, the oracle is constructed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>Mn<\/jats:italic>\n            <jats:sup>3.376\u2212\u03b1<\/jats:sup>\n            ) time with\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\u2212(1\u2212\u03b1)\/|S|<\/jats:sup>\n            ) query, or alternatively in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>M<\/jats:italic>\n            <jats:sup>0.681<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3.575\u2212\u03b1<\/jats:sup>\n            ) time with\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\u22122(1\u2212\u03b1)\/|S|<\/jats:sup>\n            ) query.\n          <\/jats:p>\n          <jats:p>\n            Distance sensitivity oracles generalize the\n            <jats:italic>replacement paths<\/jats:italic>\n            problem in which\n            <jats:italic>u<\/jats:italic>\n            and\n            <jats:italic>v<\/jats:italic>\n            are known in advance and |\n            <jats:italic>S<\/jats:italic>\n            | = 1. In other words, if\n            <jats:italic>P<\/jats:italic>\n            is a shortest path from\n            <jats:italic>u<\/jats:italic>\n            to\n            <jats:italic>v<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            , then the replacement paths problem asks to compute, for every edge\n            <jats:italic>e<\/jats:italic>\n            on\n            <jats:italic>P<\/jats:italic>\n            , a shortest\n            <jats:italic>u<\/jats:italic>\n            -to-\n            <jats:italic>v<\/jats:italic>\n            path that avoids\n            <jats:italic>e<\/jats:italic>\n            . Our new technique for constructing distance sensitivity oracles using fast matrix multiplication also yields the first subcubic-time algorithm for the replacement paths problem when the edge-lengths are small integers. In particular, it yields a randomized (Monte Carlo)\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>Mn<\/jats:italic>\n            <jats:sup>2.376<\/jats:sup>\n            +\n            <jats:italic>M<\/jats:italic>\n            <jats:sup>2 3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.584<\/jats:sup>\n            )-time algorithm for the replacement paths problem assuming\n            <jats:italic>M<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.624<\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            Finally, we mention that both our replacement paths algorithm and our distance sensitivity oracle can be made to work, in the same time and space bounds, for the case of failed vertices rather than edges, that is, when\n            <jats:italic>S<\/jats:italic>\n            is a set of vertices and we seek a shortest\n            <jats:italic>u<\/jats:italic>\n            -to-\n            <jats:italic>v<\/jats:italic>\n            path in the graph obtained from\n            <jats:italic>G<\/jats:italic>\n            by removing all vertices in\n            <jats:italic>S<\/jats:italic>\n            and their adjacent edges.\n          <\/jats:p>","DOI":"10.1145\/2438645.2438646","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication"],"prefix":"10.1145","volume":"9","author":[{"given":"Oren","family":"Weimann","sequence":"first","affiliation":[{"name":"University of Haifa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[{"name":"University of Haifa"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd Ed. Wiley-Interscience.  Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd Ed. Wiley-Interscience.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1388"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873662"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). 34--43","author":"Bernstein A."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA). 84--96","author":"Chechik S."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium On Discrete Algorithms (SODA). 362--371","author":"Demetrescu C."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 506--515","author":"Duan R."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). 428--435","author":"Emek Y."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.12.015"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 42nd Annual Symposium on Foundations Of Computer Science (FOCS). 252--259","author":"Hershberger J."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS). 343--354","author":"Hershberger J."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222071"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 236--245","author":"Klein P."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00175-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00438-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 920--4928","author":"Roditty L.","year":"2007"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_21"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_33"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060607"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 1337--1346","author":"Vassilevska-Williams V.","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.68"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873663"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.20"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90085-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2438645.2438646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:29Z","timestamp":1750235729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2438645.2438646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2438645.2438646"],"URL":"https:\/\/doi.org\/10.1145\/2438645.2438646","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}