{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985404,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["24-1323-A0001"],"award-info":[{"award-number":["24-1323-A0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733513","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"287-298","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Distributed Replacement Paths"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8068-1649","authenticated-orcid":false,"given":"Yanyu","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0675-8790","authenticated-orcid":false,"given":"Dipan","family":"Dey","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0540-0292","authenticated-orcid":false,"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7993-2952","authenticated-orcid":false,"given":"Hung Thuan","family":"Nguyen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5807-297X","authenticated-orcid":false,"given":"Bryce","family":"Sanchez","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Even in Sparse Networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science","volume":"42","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science, Vol. 9888), Cyril Gavoille and David Ilcinkas (Eds.). Springer, 29\u201342."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188888"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400256"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212773"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs","volume":"17","author":"Ancona Bertie","year":"2020","unstructured":"Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, and Virginia Vassilevska Williams. 2020. Distributed Distance Approximation. In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 184), Quentin Bramas, Rotem Oshman, and Paolo Romano (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 30:1\u201330:17."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 32nd Annual European Symposium on Algorithms (ESA) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"15","author":"Ashvinkumar Vikrant","year":"2024","unstructured":"Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin-Hao Su. 2024. Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 308), Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 13:1\u201313:15."},{"key":"e_1_3_2_1_7_1","volume-title":"Karger","author":"Bernstein Aaron","year":"2008","unstructured":"Aaron Bernstein and David R. Karger. 2008. Improved distance sensitivity oracles via random sampling. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Shang-Hua Teng (Ed.). SIAM, 34\u201343."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316326"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems.","author":"Bhosle Amit M","year":"2004","unstructured":"Amit M Bhosle and Teofilo F Gonzalez. 2004. Replacement paths for pairs of shortest path edges in directed graphs. In Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems."},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 29th Annual European Symposium on Algorithms (ESA) (LIPIcs","volume":"17","author":"Bil\u00f3 Davide","year":"2021","unstructured":"Davide Bil\u00f3, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2021. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA) (LIPIcs, Vol. 204), Petra Mutzel, Rasmus Pagh, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:17."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603542"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Cao Nairen","unstructured":"Nairen Cao and Jeremy T. Fineman. 2023. Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Florence, Italy, 4354\u20134372."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.171"},{"key":"e_1_3_2_1_14_1","volume-title":"Hung Thuan Nguyen, and Bryce Sanchez","author":"Chang Yi-Jun","year":"2025","unstructured":"Yi-Jun Chang, Yanyu Chen, Dipan Dey, Gopinath Mishra, Hung Thuan Nguyen, and Bryce Sanchez. 2025. Optimal Distributed Replacement Paths. CoRR abs\/2502.15378 (2025). arXiv:2502.15378"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.126"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs","volume":"17","author":"Chechik Shiri","year":"2020","unstructured":"Shiri Chechik and Ofer Magen. 2020. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 81:1\u201381:17."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"13","author":"Chechik Shiri","year":"2019","unstructured":"Shiri Chechik and Doron Mukhtar. 2019. Reachability and Shortest Paths in the Broadcast CONGEST Model. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 11:1\u201311:13."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405729"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC). 363\u2013372","author":"Sarma Atish Das","year":"2011","unstructured":"Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed verification and hardness of distributed approximation. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC). 363\u2013372."},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 30th Annual European Symposium on Algorithms (ESA) (LIPIcs","volume":"18","author":"Dey Dipan","year":"2022","unstructured":"Dipan Dey and Manoj Gupta. 2022. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA) (LIPIcs, Vol. 244), Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 42:1\u201342:18."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405735"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387161"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00071"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188948"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935795"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"16","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter. 2017. Near-Optimal Distributed DFS in Planar Graphs. In Proceedings of the 31st International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 91), Andr\u00e9a Richa (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 21:1\u201321:16."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.17"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365835"},{"key":"e_1_3_2_1_30_1","unstructured":"Daniel H Greene and Donald E Knuth. 2007. Mathematics for the Analysis of Algorithms: Modern Birkhuser Classics."},{"key":"e_1_3_2_1_31_1","volume-title":"Virginia Vassilevska Williams, and Yinzhan Xu","author":"Gu Yuzhou","year":"2021","unstructured":"Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, and Yinzhan Xu. 2021. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 198), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 75:1\u201375:20."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405714"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520026"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451081"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959899"},{"key":"e_1_3_2_1_36_1","volume-title":"On the Difficulty of Some Shortest Path Problems. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (Lecture Notes in Computer Science","volume":"354","author":"Hershberger John","unstructured":"John Hershberger, Subhash Suri, and Amit M. Bhosle. 2003. On the Difficulty of Some Shortest Path Problems. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (Lecture Notes in Computer Science, Vol. 2607), Helmut Alt and Michel Habib (Eds.). Springer, 343\u2013354."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 168\u2013179","author":"Huang Chien-Chung","year":"2017","unstructured":"Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. 2017. Distributed Exact Weighted All-Pairs Shortest Paths in \u00d5(n5\/4) Rounds. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 168\u2013179."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1664\u20131686","author":"Jambulapati Arun","year":"2019","unstructured":"Arun Jambulapati, Yang P Liu, and Aaron Sidford. 2019. Parallel reachability in almost linear work and square root depth. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1664\u20131686."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767398"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0326-6"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662158.3662801"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-60603-8_23"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91736-3_22"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00438-3"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"17","author":"Parter Merav","year":"2020","unstructured":"Merav Parter. 2020. Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers. In Proceedings of the 34th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 179), Hagit Attiya (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 21:1\u201321:17."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520047"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344423"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585235"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/97444.97686"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438646"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00090"},{"key":"e_1_3_2_1_58_1","volume-title":"Finding the k shortest loopless paths in a network. management Science 17, 11","author":"Yen Jin Y","year":"1971","unstructured":"Jin Y Yen. 1971. Finding the k shortest loopless paths in a network. management Science 17, 11 (1971), 712\u2013716."}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:03Z","timestamp":1749824703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":58,"alternative-id":["10.1145\/3732772.3733513","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733513","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}