{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:06Z","timestamp":1750306326278,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T00:00:00Z","timestamp":1516579200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ISF","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-CORE program of the Israel PBC"},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology"},{"name":"Google European Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"<jats:p>\n            A\n            <jats:italic>fault-tolerant<\/jats:italic>\n            structure for a network is required to continue functioning following the failure of some of the network\u2019s edges or vertices. This article addresses the problem of designing a\n            <jats:italic>fault-tolerant<\/jats:italic>\n            (\u03b1 , \u03b2) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph\n            <jats:italic>H<\/jats:italic>\n            of the network\n            <jats:italic>G<\/jats:italic>\n            such that subsequent to the failure of some subset\n            <jats:italic>F<\/jats:italic>\n            of edges or vertices, the surviving part of\n            <jats:italic>H<\/jats:italic>\n            (namely,\n            <jats:italic>H \\ F<\/jats:italic>\n            ) still contains an\n            <jats:italic>approximate<\/jats:italic>\n            BFS spanning tree for (the surviving part of)\n            <jats:italic>G<\/jats:italic>\n            , satisfying dist(\n            <jats:italic>s,v,H \\ F<\/jats:italic>\n            ) \u2264\n            <jats:italic>\u03b1<\/jats:italic>\n            \u010b dist(\n            <jats:italic>s,v,G \\ F<\/jats:italic>\n            )+\n            <jats:italic>\u03b2<\/jats:italic>\n            for every\n            <jats:italic>v<\/jats:italic>\n            isin\n            <jats:italic>V<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Our first result is an algorithm that given an\n            <jats:italic>n<\/jats:italic>\n            -vertex unweighted undirected graph\n            <jats:italic>G<\/jats:italic>\n            and a source\n            <jats:italic>s<\/jats:italic>\n            constructs a\n            <jats:italic>multiplicative<\/jats:italic>\n            (3,0) FT-ABFS structure rooted at\n            <jats:italic>s<\/jats:italic>\n            resilient to a failure of a\n            <jats:italic>single<\/jats:italic>\n            edge with at most 4\n            <jats:italic>n<\/jats:italic>\n            edges (improving by an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) factor on the near-tight result of Baswana and Khanna (2010) for the special case of edge failures). This was recently improved to 2n edges by Bil\u00f2 et al. (2014). Next, we consider the multiple edge faults case, for a constant integer\n            <jats:italic>f<\/jats:italic>\n            &gt;1, we prove that there exists a (polynomial-time constructible) (3\n            <jats:italic>f<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) FT-ABFS structure with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            ) edges that is resilient against\n            <jats:italic>f<\/jats:italic>\n            faults. We also show the existence of a (3\n            <jats:italic>f<\/jats:italic>\n            +1,0) FT-ABFS structure with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            log\n            <jats:sup>f<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            \u010b\n            <jats:italic>n<\/jats:italic>\n            ) edges.\n          <\/jats:p>\n          <jats:p>\n            We then consider\n            <jats:italic>additive<\/jats:italic>\n            (1,\n            <jats:italic>\u03b2<\/jats:italic>\n            ) FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of (\n            <jats:italic>\u03b1<\/jats:italic>\n            ,0) FT-ABFS structures, we show that for every\n            <jats:italic>n<\/jats:italic>\n            , there exist\n            <jats:italic>\u03b4<\/jats:italic>\n            , \u03b5 &gt;0, and\n            <jats:italic>n<\/jats:italic>\n            -vertex graphs\n            <jats:italic>G<\/jats:italic>\n            with a source\n            <jats:italic>s<\/jats:italic>\n            for which any (1,\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b4<\/jats:sup>\n            ) FT-ABFS structure rooted at\n            <jats:italic>s<\/jats:italic>\n            has \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>7\/6<\/jats:sup>\n            \u2212\u03b5) edges. For the case of additive stretch 3, we show that (1,3) FT-ABFS structures admit a lower bound of \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5\/4<\/jats:sup>\n            ) edges.\n          <\/jats:p>","DOI":"10.1145\/3022730","type":"journal-article","created":{"date-parts":[[2018,1,22]],"date-time":"2018-01-22T13:22:59Z","timestamp":1516627379000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Fault-Tolerant Approximate BFS Structures"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2357-2445","authenticated-orcid":false,"given":"Merav","family":"Parter","sequence":"first","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ittai Abraham and Cyril Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In Distributed Computing. SV 404--415.   Ittai Abraham and Cyril Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In Distributed Computing. SV 404--415.","DOI":"10.1007\/978-3-642-24100-0_39"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.29"},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. 672--681","year":"2005","author":"Baswana Surender","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","year":"2010","author":"Baswana Surender","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873662"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_15"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_12"},{"volume-title":"Preserving distances in very faulty graphs. arXiv:1703.10293","year":"2017","author":"Bodwin Greg","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684068"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.036"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627853"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9543-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4064\/cm-13-2-251-254"},{"volume-title":"Royle","year":"2013","author":"Godsil Chris","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875576"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0252-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_66"},{"volume-title":"Fault-tolerant approximate BFS structures. arXiv:1406.6169","year":"2014","author":"Parter Merav","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634154"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.83"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90097-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022730","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3022730","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:31Z","timestamp":1750222471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022730"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,22]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3022730"],"URL":"https:\/\/doi.org\/10.1145\/3022730","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,1,22]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}