{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:46:13Z","timestamp":1772120773325,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,10,10]],"date-time":"2016-10-10T00:00:00Z","timestamp":1476057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005386","name":"I-CORE","doi-asserted-by":"crossref","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"<jats:p>\n            A\n            <jats:italic>fault-tolerant<\/jats:italic>\n            structure for a network is required for continued functioning following the failure of some of the network\u2019s edges or vertices. This article considers\n            <jats:italic>breadth-first search (BFS)<\/jats:italic>\n            spanning trees and addresses the problem of designing a sparse\n            <jats:italic>fault-tolerant<\/jats:italic>\n            BFS structure (FT-BFS structure), namely, a sparse subgraph\n            <jats:italic>T<\/jats:italic>\n            of the given network\n            <jats:italic>G<\/jats:italic>\n            such that subsequent to the failure of a single edge or vertex, the surviving part\n            <jats:italic>T<\/jats:italic>\n            \u2032 of\n            <jats:italic>T<\/jats:italic>\n            still contains a BFS spanning tree for (the surviving part of)\n            <jats:italic>G<\/jats:italic>\n            . For a source node\n            <jats:italic>s<\/jats:italic>\n            , a target node\n            <jats:italic>t<\/jats:italic>\n            , and an edge\n            <jats:italic>e<\/jats:italic>\n            \u2208\n            <jats:italic>G<\/jats:italic>\n            , the shortest\n            <jats:italic>s<\/jats:italic>\n            \u2212\n            <jats:italic>t<\/jats:italic>\n            path\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n              ,\n              <jats:italic>t<\/jats:italic>\n              ,\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            that does not go through\n            <jats:italic>e<\/jats:italic>\n            is known as a\n            <jats:italic>replacement path<\/jats:italic>\n            . Thus, our FT-BFS structure contains the collection of all replacement paths\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n              ,\n              <jats:italic>t<\/jats:italic>\n              ,\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            for every\n            <jats:italic>t<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) and every failed edge\n            <jats:italic>e<\/jats:italic>\n            \u2208\n            <jats:italic>E<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ). Our main results are as follows. We present an algorithm that for every\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            and source node\n            <jats:italic>s<\/jats:italic>\n            constructs a (single edge failure) FT-BFS structure rooted at\n            <jats:italic>s<\/jats:italic>\n            with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u010b min {Depth(\n            <jats:italic>s<\/jats:italic>\n            ), \u221an{) edges, where Depth(\n            <jats:italic>s<\/jats:italic>\n            ) is the depth of the BFS tree rooted at\n            <jats:italic>s<\/jats:italic>\n            . This result is complemented by a matching lower bound, showing that there exist\n            <jats:italic>n<\/jats:italic>\n            -vertex graphs with a source node\n            <jats:italic>s<\/jats:italic>\n            for which any edge (or vertex) FT-BFS structure rooted at\n            <jats:italic>s<\/jats:italic>\n            has \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) edges. We then consider\n            <jats:italic>fault-tolerant multi-source BFS structures<\/jats:italic>\n            (FT-MBFS structures), aiming to provide (following a failure) a BFS tree rooted at each source\n            <jats:italic>s<\/jats:italic>\n            \u2208\n            <jats:italic>S<\/jats:italic>\n            for some subset of sources\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            . Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every\n            <jats:italic>n<\/jats:italic>\n            -vertex graph and source set\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            of size \u03c3 constructs a (single failure) FT-MBFS structure\n            <jats:italic>T<\/jats:italic>\n            *(\n            <jats:italic>S<\/jats:italic>\n            ) from each source\n            <jats:italic>\n              s\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2208\n            <jats:italic>S<\/jats:italic>\n            , with\n            <jats:italic>O<\/jats:italic>\n            (\u221a\u03c3 \u010b\n            <jats:italic>n<\/jats:italic>\n            &lt;sup;&gt;3\/2&lt;\/sup;&gt;) edges, and, on the other hand, there exist\n            <jats:italic>n<\/jats:italic>\n            -vertex graphs with source sets\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            of cardinality \u03c3, on which any FT-MBFS structure from\n            <jats:italic>S<\/jats:italic>\n            has \u03a9(\u221a\u03c3 \u010b\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) edges. Finally, we propose an\n            <jats:italic>O<\/jats:italic>\n            (log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no \u03a9(log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) approximation algorithm for these problems under standard complexity assumptions. In comparison with previous constructions, our algorithm is deterministic and may improve the number of edges by a factor of up to \u221a\n            <jats:italic>n<\/jats:italic>\n            for some instances. All our algorithms can be extended to deal with one\n            <jats:italic>vertex<\/jats:italic>\n            failure as well, with the same performance.\n          <\/jats:p>","DOI":"10.1145\/2976741","type":"journal-article","created":{"date-parts":[[2016,10,11]],"date-time":"2016-10-11T18:01:35Z","timestamp":1476208895000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Sparse Fault-Tolerant BFS Structures"],"prefix":"10.1145","volume":"13","author":[{"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":[[2016,10,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115966.3116122"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835743"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73053"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.29"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_2_1_7_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Chechik Shiri"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2220253.2220258"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3115997"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496826"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.17"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875576"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276734"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645932.673192"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05118-0_3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344423"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.68"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2976741","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2976741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:16Z","timestamp":1750222576000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2976741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,10]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2976741"],"URL":"https:\/\/doi.org\/10.1145\/2976741","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,10]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}