{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:25Z","timestamp":1750220665130,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"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":[],"published-print":{"date-parts":[[2020,7,31]]},"DOI":"10.1145\/3382734.3405714","type":"proceedings-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T22:33:55Z","timestamp":1596234835000},"page":"339-348","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Multiple Source Replacement Path Problem"],"prefix":"10.1145","author":[{"given":"Manoj","family":"Gupta","sequence":"first","affiliation":[{"name":"IIT Gandhinagar"}]},{"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[{"name":"Goldman Sachs, Bangalore"}]},{"given":"Nitiksha","family":"Modi","sequence":"additional","affiliation":[{"name":"IIT Gandhinagar"}]}],"member":"320","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/777474.777480"},{"key":"e_1_3_2_1_2_1","first-page":"88","volume-title":"LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000","author":"Michael","year":"2000","unstructured":"Michael A. Bender and Martin Farach-Colton. The LCA problem revisited . In LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 , Proceedings , pages 88 -- 94 , 2000 . Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, pages 88--94, 2000."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873662"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_3_2_1_5_1","first-page":"34","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"Bernstein Aaron","year":"2008","unstructured":"Aaron Bernstein and David R. Karger . Improved distance sensitivity oracles via random sampling. In Shang-Hua Teng, editor , Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008 , San Francisco, California, USA , January 20-22, 2008 , pages 34 -- 43 . SIAM, 2008. Aaron Bernstein and David R. Karger. Improved distance sensitivity oracles via random sampling. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 34--43. SIAM, 2008."},{"key":"e_1_3_2_1_6_1","first-page":"1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science, STACS 2018","author":"Bil\u00f2 Davide","year":"2018","unstructured":"Davide Bil\u00f2 , Keerti Choudhary , Luciano Gual\u00e0 , Stefano Leucci , Merav Parter , and Guido Proietti . Efficient oracles and routing schemes for replacement paths . In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 , February 28 to March 3, 2018 , Caen, France, pages 13: 1 -- 13 :15, 2018. Davide Bil\u00f2, Keerti Choudhary, Luciano Gual\u00e0, Stefano Leucci, Merav Parter, and Guido Proietti. Efficient oracles and routing schemes for replacement paths. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 13:1--13:15, 2018."},{"key":"e_1_3_2_1_7_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","author":"Bodwin Greg","year":"2017","unstructured":"Greg Bodwin , Fabrizio Grandoni , Merav Parter , and Virginia Vassilevska Williams . Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , July 10-14, 2017 , Warsaw, Poland, pages 73:1--73:14 , 2017. Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 73:1--73:14, 2017."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.126"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Chechik Shiri","year":"2017","unstructured":"Shiri Chechik , Sarel Cohen , Amos Fiat , and Haim Kaplan . (1 + \u2208)-approximate f-sensitive distance oracles . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1479--1496 , 2017 . Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + \u2208)-approximate f-sensitive distance oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1479--1496, 2017."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.56"},{"key":"e_1_3_2_1_13_1","volume-title":"A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms (TALG), 6(4):64","author":"Emek Yuval","year":"2010","unstructured":"Yuval Emek , David Peleg , and Liam Roditty . A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms (TALG), 6(4):64 , 2010 . Yuval Emek, David Peleg, and Liam Roditty. A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms (TALG), 6(4):64, 2010."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365697"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.12.015"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.17"},{"key":"e_1_3_2_1_18_1","volume-title":"Multiple source replacement path problem. arXiv preprint arXiv:2005.09262","author":"Gupta Manoj","year":"2020","unstructured":"Manoj Gupta , Rahul Jain , and Nitiksha Modi . Multiple source replacement path problem. arXiv preprint arXiv:2005.09262 , 2020 . Manoj Gupta, Rahul Jain, and Nitiksha Modi. Multiple source replacement path problem. arXiv preprint arXiv:2005.09262, 2020."},{"key":"e_1_3_2_1_19_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","author":"Gupta Manoj","year":"2017","unstructured":"Manoj Gupta and Shahbaz Khan . Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , July 10-14, 2017 , Warsaw, Poland, pages 127:1--127:15 , 2017. Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 127:1--127:15, 2017."},{"key":"e_1_3_2_1_20_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Gupta Manoj","year":"2018","unstructured":"Manoj Gupta and Aditi Singh . Generic single edge fault tolerant exact distance oracle. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018 , Prague, Czech Republic, pages 72:1--72:15 , 2018. Manoj Gupta and Aditi Singh. Generic single edge fault tolerant exact distance oracle. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 72:1--72:15, 2018."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959899"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00438-3"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767408"},{"key":"e_1_3_2_1_27_1","first-page":"779","volume-title":"Sophia Antipolis","author":"Parter Merav","year":"2013","unstructured":"Merav Parter and David Peleg . Sparse fault-tolerant BFS trees. In Algorithms - ESA 2013 - 21st Annual European Symposium , Sophia Antipolis , France , September 2-4, 2013 . Proceedings, pages 779 -- 790 , 2013. Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 779--790, 2013."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283482"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_3_2_1_30_1","volume-title":"Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms (TALG), 8(4):33","author":"Roditty Liam","year":"2012","unstructured":"Liam Roditty and Uri Zwick . Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms (TALG), 8(4):33 , 2012 . Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms (TALG), 8(4):33, 2012."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133138"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"}],"event":{"name":"PODC '20: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '20"},"container-title":["Proceedings of the 39th Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3405714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:49Z","timestamp":1750197769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":33,"alternative-id":["10.1145\/3382734.3405714","10.1145\/3382734"],"URL":"https:\/\/doi.org\/10.1145\/3382734.3405714","relation":{},"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"2020-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}