{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:27Z","timestamp":1750219827083,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T00:00:00Z","timestamp":1696982400000},"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":["J. ACM"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>restoration lemma<\/jats:italic>\n            by Afek et\u00a0al. [\n            <jats:xref ref-type=\"bibr\">3<\/jats:xref>\n            ] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is\n            <jats:italic>tiebreaking-sensitive<\/jats:italic>\n            : if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two\n            <jats:italic>selected<\/jats:italic>\n            shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible.\n          <\/jats:p>\n          <jats:p>\n            We settle this question affirmatively with the first general construction of\n            <jats:italic>restorable tiebreaking schemes<\/jats:italic>\n            . We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, fault-tolerant subset distance preservers and + 4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to\n            <jats:italic>three<\/jats:italic>\n            faults.\n          <\/jats:p>","DOI":"10.1145\/3603542","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T11:20:07Z","timestamp":1691580007000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9896-8906","authenticated-orcid":false,"given":"Greg","family":"Bodwin","sequence":"first","affiliation":[{"name":"University of Michigan EECS, Ann Arbor, MI"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2357-2445","authenticated-orcid":false,"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2023,10,11]]},"reference":[{"key":"e_1_3_5_2_2","first-page":"1199","volume-title":"44th Annual ACM Symposium on Theory of Computing","author":"Abraham Ittai","year":"2012","unstructured":"Ittai Abraham, Shiri Chechik, and Cyril Gavoille. 2012. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In 44th Annual ACM Symposium on Theory of Computing. 1199\u20131218."},{"key":"e_1_3_5_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2818694"},{"key":"e_1_3_5_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/777474.777480"},{"key":"e_1_3_5_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"e_1_3_5_6_2","first-page":"13:1\u201313:15","volume-title":"35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France","author":"Bil\u00f2 Davide","year":"2018","unstructured":"Davide Bil\u00f2, Keerti Choudhary, Luciano Gual\u00e0, Stefano Leucci, Merav Parter, and Guido Proietti. 2018. 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. 13:1\u201313:15."},{"key":"e_1_3_5_7_2","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS\u201918)","author":"Bil\u00f2 Davide","year":"2018","unstructured":"Davide Bil\u00f2, Keerti Choudhary, Luciano Gual\u00e0, Stefano Leucci, Merav Parter, and Guido Proietti. 2018. Efficient oracles and routing schemes for replacement paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS\u201918). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_5_8_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-662-48350-3_15","volume-title":"Algorithms-ESA 2015","author":"Bil\u00f2 Davide","year":"2015","unstructured":"Davide Bil\u00f2, Fabrizio Grandoni, Luciano Gual\u00e0, Stefano Leucci, and Guido Proietti. 2015. Improved purely additive fault-tolerant spanners. In Algorithms-ESA 2015. Springer, 167\u2013178."},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.15"},{"key":"e_1_3_5_10_2","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Bodwin Greg","year":"2017","unstructured":"Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. 2017. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_5_11_2","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/978-3-642-34611-8_22","volume-title":"International Workshop on Graph-Theoretic Concepts in Computer Science","author":"Braunschvig Gilad","year":"2012","unstructured":"Gilad Braunschvig, Shiri Chechik, and David Peleg. 2012. Fault tolerant additive spanners. In International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 206\u2013214."},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/2781925.2782542"},{"key":"e_1_3_5_13_2","first-page":"2090","volume-title":"30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chechik Shiri","year":"2019","unstructured":"Shiri Chechik and Sarel Cohen. 2019. Near optimal algorithms for the single source replacement paths problem. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2090\u20132109."},{"key":"e_1_3_5_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.96"},{"key":"e_1_3_5_15_2","volume-title":"2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY) (Co-located with PODC)","author":"Courcelle Bruno","year":"2007","unstructured":"Bruno Courcelle, Cyril Gavoille, M. Kant\u00e9, and Andrew Twigg. 2007. Forbidden-set labeling on graphs. In 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY) (Co-located with PODC)."},{"key":"e_1_3_5_16_2","first-page":"37","volume-title":"Annual Symposium on Theoretical Aspects of Computer Science","author":"Courcelle Bruno","year":"2007","unstructured":"Bruno Courcelle and Andrew Twigg. 2007. Compact forbidden-set routing. In Annual Symposium on Theoretical Aspects of Computer Science. Springer, 37\u201348."},{"key":"e_1_3_5_17_2","first-page":"169","volume-title":"30th Annual ACM Symposium on Principles of Distributed Computing (PODC 2011) (San Jose, CA, June 6\u20138)","author":"Dinitz Michael","year":"2011","unstructured":"Michael Dinitz and Robert Krauthgamer. 2011. Fault-tolerant spanners: Better and simpler. In 30th Annual ACM Symposium on Principles of Distributed Computing (PODC 2011) (San Jose, CA, June 6\u20138). 169\u2013178."},{"key":"e_1_3_5_18_2","volume-title":"ACM Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Dinitz Michael","year":"2020","unstructured":"Michael Dinitz and Caleb Robelle. 2020. Efficient and simple algorithms for fault-tolerant spanners. In ACM Symposium on Principles of Distributed Computing (PODC\u201920)."},{"key":"e_1_3_5_19_2","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/11600930_18","volume-title":"International Workshop on Internet and Network Economics","author":"Feigenbaum Joan","year":"2005","unstructured":"Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, and Rahul Sami. 2005. Subjective-cost policy routing. In International Workshop on Internet and Network Economics. Springer, 174\u2013183."},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_3_5_21_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2767386.2767417","volume-title":"2015 ACM Symposium on Principles of Distributed Computing","author":"Ghaffari Mohsen","year":"2015","unstructured":"Mohsen Ghaffari. 2015. Near-optimal scheduling of distributed algorithms. In 2015 ACM Symposium on Principles of Distributed Computing. 3\u201312."},{"key":"e_1_3_5_22_2","first-page":"387","volume-title":"28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016) (Asilomar State Beach\/Pacific Grove, CA, July 11\u201313)","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari and Merav Parter. 2016. Near-optimal distributed algorithms for fault-tolerant tree structures. In 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016) (Asilomar State Beach\/Pacific Grove, CA, July 11\u201313). 387\u2013396."},{"key":"e_1_3_5_23_2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/3382734.3405714","volume-title":"39th Symposium on Principles of Distributed Computing","author":"Gupta Manoj","year":"2020","unstructured":"Manoj Gupta, Rahul Jain, and Nitiksha Modi. 2020. Multiple source replacement path problem. In 39th Symposium on Principles of Distributed Computing. 339\u2013348."},{"key":"e_1_3_5_24_2","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","author":"Gupta Manoj","year":"2017","unstructured":"Manoj Gupta and Shahbaz Khan. 2017. Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_5_25_2","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/SFCS.2001.959899","volume-title":"42nd IEEE Symposium on Foundations of Computer Science","author":"Hershberger John","year":"2001","unstructured":"John Hershberger and Subhash Suri. 2001. Vickrey prices and shortest paths: What is an edge worth?. In 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 252\u2013259."},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_3_5_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"e_1_3_5_28_2","first-page":"345","volume-title":"19th Annual ACM Symposium on Theory of Computing","author":"Mulmuley Ketan","year":"1987","unstructured":"Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. 1987. Matching is as easy as matrix inversion. In 19th Annual ACM Symposium on Theory of Computing. 345\u2013354."},{"key":"e_1_3_5_29_2","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/2767386.2767408","volume-title":"2015 ACM Symposium on Principles of Distributed Computing","author":"Parter Merav","year":"2015","unstructured":"Merav Parter. 2015. Dual failure resilient BFS structure. In 2015 ACM Symposium on Principles of Distributed Computing. 481\u2013490."},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0252-9"},{"key":"e_1_3_5_31_2","first-page":"21:1\u201321:17","volume-title":"34th International Symposium on Distributed Computing (DISC 2020) (October 12\u201316, 2020, Virtual Conference)","author":"Parter Merav","year":"2020","unstructured":"Merav Parter. 2020. Distributed constructions of dual-failure fault-tolerant distance preservers. In 34th International Symposium on Distributed Computing (DISC 2020) (October 12\u201316, 2020, Virtual Conference). 21:1\u201321:17."},{"key":"e_1_3_5_32_2","first-page":"1073","volume-title":"25th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Parter Merav","year":"2014","unstructured":"Merav Parter and David Peleg. 2014. Fault tolerant approximate BFS structures. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1073\u20131092."},{"key":"e_1_3_5_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_5_34_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/28.1.5"},{"key":"e_1_3_5_35_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1078"},{"key":"e_1_3_5_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"e_1_3_5_37_2","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1109\/FOCS.2019.00034","volume-title":"2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Brand Jan van den","year":"2019","unstructured":"Jan van den Brand and Thatchaphol Saranurak. 2019. Sensitive distance and reachability oracles for large batch updates. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS\u201919). IEEE, 424\u2013435."},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.68"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438646"},{"key":"e_1_3_5_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3603542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:26Z","timestamp":1750178786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,11]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3603542"],"URL":"https:\/\/doi.org\/10.1145\/3603542","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,10,11]]},"assertion":[{"value":"2021-09-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}