{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:56Z","timestamp":1761621056617},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> Let G be an undirected graph with m edges and n vertices. A spanner of G is a subgraph which preserves approximate distances between all pairs of vertices. An f-vertex fault-tolerant spanner is a subgraph which preserves approximate distances, under the failure of any set of at most f vertices. The contribution of this paper is twofold: we present algorithms for computing fault-tolerant spanners, and propose streaming algorithms for computing spanners in very small internal memory. In particular, we give algorithms for computing f-vertex fault-tolerant (3,2)- and (2,1)-spanners of G with the following bounds: our (3,2)-spanner contains O(f<jats:sup>4\/3<\/jats:sup>n<jats:sup>4\/3<\/jats:sup>) edges and can be computed in time \u00d5(f<jats:sup>2<\/jats:sup>m), while our(2, 1)-spanner contains O(fn<jats:sup>3\/2<\/jats:sup>) edges and can be computed in time [Formula: see text]. Both algorithms improve significantly on previously known bounds. <\/jats:p><jats:p> Assume that the graph G is presented as an input stream of edges, which may appear in any arbitrary order, and that we do not know in advance m and n. We show how to compute efficiently (3, 2)- and (2, 1)-spanners of G, using only very small internal memory and as low access external memory device. Our spanners have asymptotically optimal size and the I\/O complexity of our algorithms for computing such spanners is optimal upto apolylogarithmic factor. Our f-vertex fault-tolerant (3, 2)- and (2, 1)-spanners can also be computed efficiently in the same computational model described above. <\/jats:p>","DOI":"10.1142\/s1793830910000905","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T08:21:26Z","timestamp":1295252486000},"page":"591-605","source":"Crossref","is-referenced-by-count":7,"title":["COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING"],"prefix":"10.1142","volume":"02","author":[{"given":"GIORGIO","family":"AUSIELLO","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica, Sapienza Universit\u00e0 di Roma, via Ariosto 25, I-00185 Roma, Italy"}]},{"given":"ANDREA","family":"RIBICHINI","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica e Sistemistica, Sapienza Universit\u00e0 di Roma, via Ariosto 25, I-00185 Roma, Italy"}]},{"given":"PAOLO G.","family":"FRANCIOSA","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze Statistiche, Sapienza Universit\u00e0 di Roma, piazzale Aldo Moro 5, I-00185 Roma, Italy"}]},{"given":"GIUSEPPE F.","family":"ITALIANO","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemi e Produzione, Universit\u00e0 di Roma \"Tor Vergata\", via del Politecnico 1, 00133 Roma, Italy"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9216-9"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00133"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.022"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230417"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2641"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:16:06Z","timestamp":1565111766000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":13,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S1793830910000905"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000905","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}