{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T10:37:26Z","timestamp":1773830246866,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>\n            Spanner of an undirected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V,E<\/jats:italic>\n            ) is a subgraph that is sparse and yet preserves all-pairs distances approximately. More formally, a spanner with\n            <jats:italic>stretch<\/jats:italic>\n            <jats:italic>t<\/jats:italic>\n            \u2208 \u2115 is a subgraph (\n            <jats:italic>\n              V,E\n              <jats:sub>S<\/jats:sub>\n            <\/jats:italic>\n            ),\n            <jats:italic>\n              E\n              <jats:sub>S<\/jats:sub>\n            <\/jats:italic>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            such that the distance between any two vertices in the subgraph is at most\n            <jats:italic>t<\/jats:italic>\n            times their distance in\n            <jats:italic>G<\/jats:italic>\n            . Though\n            <jats:italic>G<\/jats:italic>\n            is trivially a\n            <jats:italic>t<\/jats:italic>\n            -spanner of itself, the research as well as applications of spanners invariably deal with a\n            <jats:italic>t<\/jats:italic>\n            -spanner that has as small number of edges as possible.\n          <\/jats:p>\n          <jats:p>We present fully dynamic algorithms for maintaining spanners in centralized as well as synchronized distributed environments. These algorithms are designed for undirected unweighted graphs and use randomization in a crucial manner.<\/jats:p>\n          <jats:p>\n            Our algorithms significantly improve the existing fully dynamic algorithms for graph spanners. The expected size (number of edges) of a\n            <jats:italic>t<\/jats:italic>\n            -spanner maintained at each stage by our algorithms matches, up to a polylogarithmic factor, the worst case optimal size of a\n            <jats:italic>t<\/jats:italic>\n            -spanner. The expected amortized time (or messages communicated in distributed environment) to process a single insertion\/deletion of an edge by our algorithms is\n            <jats:italic>close<\/jats:italic>\n            to optimal.\n          <\/jats:p>","DOI":"10.1145\/2344422.2344425","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["Fully dynamic randomized algorithms for graph spanners"],"prefix":"10.1145","volume":"8","author":[{"given":"Surender","family":"Baswana","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sumeet","family":"Khurana","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soumojit","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_48"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080737174"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748002"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 414--423","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. , Coppersmith , D. , and Elkin , M . 2003. Sparse distance preserves and additive spanners . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 414--423 . Bollob\u00e1s, B., Coppersmith, D., and Elkin, M. 2003. Sparse distance preserves and additive spanners. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 414--423."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669","author":"Coppersmith D.","unstructured":"Coppersmith , D. and Elkin , M . 2005. Sparse source-wise and pairwise distance preservers . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669 . Coppersmith, D. and Elkin, M. 2005. Sparse source-wise and pairwise distance preservers. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669."},{"key":"e_1_2_1_13_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. In Introduction to Algorithms. The MIT Press.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. In Introduction to Algorithms. The MIT Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.04.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Elkin M. 2006. A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners. CoRR abs\/cs\/0611001.  Elkin M. 2006. A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners. CoRR abs\/cs\/0611001.","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_25_1","volume-title":"Theory of Graphs and its Applications (Proc. Sympos. Smolenice","author":"Erd\u0151s P.","year":"1963","unstructured":"Erd\u0151s , P. 1964. Extremal problems in graph theory . In Theory of Graphs and its Applications (Proc. Sympos. Smolenice , 1963 ). Publ. House Czechoslovak Acad . Sci., Prague, 29--36. Erd\u0151s, P. 1964. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 29--36."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_29_1","unstructured":"Halperin S. and Zwick U. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. unpublished manuscript.  Halperin S. and Zwick U. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. unpublished manuscript."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367069"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.22"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591","author":"Roditty L.","unstructured":"Roditty , L. and Zwick , U . 2004b. On dynamic shortest paths problems . In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591 . Roditty, L. and Zwick, U. 2004b. On dynamic shortest paths problems. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_33"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880970"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344425","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344422.2344425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:39Z","timestamp":1750273659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344422.2344425"],"URL":"https:\/\/doi.org\/10.1145\/2344422.2344425","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}