{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:03Z","timestamp":1777965723442,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_10","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T09:20:54Z","timestamp":1157966454000},"page":"76-87","source":"Crossref","is-referenced-by-count":11,"title":["Dynamic Algorithms for Graph Spanners"],"prefix":"10.1007","author":[{"given":"Surender","family":"Baswana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete and Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete and Computational Geometry"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/11561071_48","volume-title":"Algorithms \u2013 ESA 2005","author":"G. Ausiello","year":"2005","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F.: Small stretch spanners on dynamic graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 532\u2013543. Springer, Heidelberg (2005)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Complexity of network synchronization. Journal of Ass. Compt. Mach. 804\u2013823 (1985)","DOI":"10.1145\/4221.4227"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1137\/S0097539794271898","volume":"28","author":"B. Awerbuch","year":"1998","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear time construction of sparse neighborhod covers. SIAM Journal on Computing\u00a028, 263\u2013277 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Baswana, S., Sen, S.: A simple linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures and Algorithms (to appear)","DOI":"10.1002\/rsa.20130"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k\u2009\u2212\u20091)-spanner of O(n\n                           1\u2009+\u20091\/k\n                           ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"10_CR7","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00d5(n2) time. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 271\u2013280 (2004)"},{"key":"10_CR8","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, London (1978)"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"J.A. Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. Journal of Combinatorial Theory, Series B\u00a016, 97\u2013105 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing\u00a028, 210\u2013236 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR11","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice,1963), pp. 29\u201336. House Czechoslovak Acad. Sci., Prague (1964)"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge-deletion problem. Journal of association for computing machinery\u00a028, 1\u20134 (1981)","journal-title":"Journal of association for computing machinery"},{"key":"10_CR13","unstructured":"Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs (unpublished manuscript, 1996)"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. Journal of Algorithms\u00a051, 122\u2013144 (2004)","journal-title":"Journal of Algorithms"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.: Graph spanners. Journal of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM Journal on Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"10_CR17","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of Assoc. Comp. Mach.\u00a036(3), 510\u2013530 (1989)","journal-title":"Journal of Assoc. Comp. Mach."},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic construction of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/978-3-540-30140-0_52","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 580\u2013591. Springer, Heidelberg (2004)"},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of Association of Computing Machinery\u00a052, 1\u201324 (2005)","journal-title":"Journal of Association of Computing Machinery"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:16:47Z","timestamp":1619493407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11841036_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}