{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:09:18Z","timestamp":1775578158321,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israeli Science Foundation","award":["2084\/18"],"award-info":[{"award-number":["2084\/18"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["949083"],"award-info":[{"award-number":["949083"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss National Foundation","award":["200021_184735"],"award-info":[{"award-number":["200021_184735"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467929","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"445-455","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Fault-Tolerant Labeling and Compact Routing Schemes"],"prefix":"10.1145","author":[{"given":"Michal","family":"Dory","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703437211"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818694"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545504"},{"key":"e_1_3_2_2_6_1","volume-title":"Fault-Tolerant Distance Labeling for Planar Graphs. SIROCCO 2021","author":"Bar-Natan Aviv","year":"2021","unstructured":"Aviv Bar-Natan , Panagiotis Charalampopoulos , Pawel Gawrychowski , Shay Mozes , and Oren Weimann . 2021 . Fault-Tolerant Distance Labeling for Planar Graphs. SIROCCO 2021 (2021). https:\/\/arxiv.org\/abs\/2102.07154 Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. 2021. Fault-Tolerant Distance Labeling for Planar Graphs. SIROCCO 2021 (2021). https:\/\/arxiv.org\/abs\/2102.07154"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347087"},{"key":"e_1_3_2_2_8_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Chechik Shiri","unstructured":"Shiri Chechik . 2011. Fault-tolerant compact routing schemes for general graphs . In International Colloquium on Automata, Languages, and Programming . Springer , 101--112. Shiri Chechik. 2011. Fault-tolerant compact routing schemes for general graphs. In International Colloquium on Automata, Languages, and Programming. Springer, 101--112."},{"key":"e_1_3_2_2_9_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1479--1496","author":"Chechik Shiri","year":"2017","unstructured":"Shiri Chechik , Sarel Cohen , Amos Fiat , and Haim Kaplan . 2017 . (1+eps)-Approximate f-Sensitive Distance Oracles . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1479--1496 . Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 2017. (1+eps)-Approximate f-Sensitive Distance Oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1479--1496."},{"key":"e_1_3_2_2_10_1","volume-title":"18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. 84--96","author":"Chechik Shiri","year":"2010","unstructured":"Shiri Chechik , Michael Langberg , David Peleg , and Liam Roditty . 2010 . f-Sensitivity Distance Oracles and Routing Schemes. In Algorithms - ESA 2010 , 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. 84--96 . Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2010. f-Sensitivity Distance Oracles and Routing Schemes. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. 84--96."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9543-0"},{"key":"e_1_3_2_2_12_1","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. 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_2_2_13_1","volume-title":"Compact Forbidden-Set Routing. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22--24, 2007, Proceedings. 37--48","author":"Courcelle Bruno","year":"2007","unstructured":"Bruno Courcelle and Andrew Twigg . 2007 . Compact Forbidden-Set Routing. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22--24, 2007, Proceedings. 37--48 . Bruno Courcelle and Andrew Twigg. 2007. Compact Forbidden-Set Routing. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22--24, 2007, Proceedings. 37--48."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545490"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808723"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.56"},{"key":"e_1_3_2_2_17_1","volume-title":"Connectivity Oracles for Graphs Subject to Vertex Failures. CoRR","author":"Duan Ran","year":"2016","unstructured":"Ran Duan and Seth Pettie . 2016. Connectivity Oracles for Graphs Subject to Vertex Failures. CoRR , Vol. abs\/ 1607 .06865 ( 2016 ). arxiv: 1607.06865 http:\/\/arxiv.org\/abs\/1607.06865 Ran Duan and Seth Pettie. 2016. Connectivity Oracles for Graphs Subject to Vertex Failures. CoRR, Vol. abs\/1607.06865 (2016). arxiv: 1607.06865 http:\/\/arxiv.org\/abs\/1607.06865"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039717"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873639"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806773"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_2_23_1","volume-title":"Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR","author":"Gibb David","year":"2015","unstructured":"David Gibb , Bruce M. Kapron , Valerie King , and Nolan Thorn . 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR , Vol. abs\/ 1509 .06464 ( 2015 ). David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, Vol. abs\/1509.06464 (2015)."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.17"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_2_28_1","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science-STACS","author":"Khanna Neelesh","year":"2010","unstructured":"Neelesh Khanna and Surender Baswana . 2010 . Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graph . In 27th International Symposium on Theoretical Aspects of Computer Science-STACS 2010. 513--524. Neelesh Khanna and Surender Baswana. 2010. Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graph. In 27th International Symposium on Theoretical Aspects of Computer Science-STACS 2010. 513--524."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_3_2_2_30_1","volume-title":"32nd International Symposium on Distributed Computing, DISC 2018","author":"Mashreghi Ali","year":"2018","unstructured":"Ali Mashreghi and Valerie King . 2018 . Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model . In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA , October 15-19, 2018. 37:1--37:17. Ali Mashreghi and Valerie King. 2018. Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. 37:1--37:17."},{"key":"e_1_3_2_2_31_1","series-title":"SIAM journal on computing","volume-title":"Small-bias probability spaces: Efficient constructions and applications","author":"Naor Joseph","year":"1993","unstructured":"Joseph Naor and Moni Naor . 1993. Small-bias probability spaces: Efficient constructions and applications . SIAM journal on computing , Vol. 22 , 4 ( 1993 ), 838--856. Joseph Naor and Moni Naor. 1993. Small-bias probability spaces: Efficient constructions and applications. SIAM journal on computing, Vol. 22, 4 (1993), 838--856."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.54"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.015"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_3"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90010-1"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000814"},{"key":"e_1_3_2_2_38_1","volume-title":"Space Efficient Edge-Fault Tolerant Routing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS","author":"Rajan Varun","year":"2012","unstructured":"Varun Rajan . 2012 . Space Efficient Edge-Fault Tolerant Routing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Varun Rajan. 2012. Space Efficient Edge-Fault Tolerant Routing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464831"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00034"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.68"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '21","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467929","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467929","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":42,"alternative-id":["10.1145\/3465084.3467929","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467929","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}