{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:09Z","timestamp":1750694709555},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s00453-013-9779-y","type":"journal-article","created":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T16:12:15Z","timestamp":1366301535000},"page":"53-65","source":"Crossref","is-referenced-by-count":2,"title":["Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree"],"prefix":"10.1007","volume":"71","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingfei","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Ning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"9779_CR1","first-page":"489","volume-title":"STOC","author":"S. Arya","year":"1995","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.H.M.: Euclidean spanners: short, thin, and lanky. In: STOC, pp. 489\u2013498 (1995)"},{"key":"9779_CR2","first-page":"291","volume-title":"SODA","author":"P.B. Callahan","year":"1993","unstructured":"Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA, pp. 291\u2013300 (1993)"},{"issue":"1","key":"9779_CR3","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/s00454-008-9115-5","volume":"41","author":"T.-H.H. Chan","year":"2009","unstructured":"Chan, T.-H.H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. Discrete Comput. Geom. 41(1), 28\u201344 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9779_CR4","first-page":"762","volume-title":"SODA","author":"T.-H.H. Chan","year":"2005","unstructured":"Chan, T.-H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: SODA, pp. 762\u2013771 (2005)"},{"key":"9779_CR5","unstructured":"Chan, T.-H.H., Li, M., Ning, L.: Incubators vs zombies: fault-tolerant, short, thin and lanky spanners for doubling metrics (2012). arXiv:1207.0892 [cs.Os]"},{"key":"9779_CR6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica 2, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"key":"9779_CR7","first-page":"435","volume-title":"STOC","author":"S. Chechik","year":"2009","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: STOC, pp. 435\u2013444 (2009)"},{"issue":"2","key":"9779_CR8","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00454-004-1121-7","volume":"32","author":"A. Czumaj","year":"2004","unstructured":"Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete Comput. Geom. 32(2), 207\u2013230 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9779_CR9","first-page":"132","volume-title":"Symposium on Computational Geometry","author":"G. Das","year":"1994","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. In: Symposium on Computational Geometry, pp. 132\u2013139 (1994)"},{"key":"9779_CR10","first-page":"169","volume-title":"PODC","author":"M. Dinitz","year":"2011","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: PODC, pp. 169\u2013178 (2011)"},{"key":"9779_CR11","first-page":"519","volume-title":"FOCS","author":"Y. Dinitz","year":"2008","unstructured":"Dinitz, Y., Elkin, M., Solomon, S.: Shallow-low-light trees, and tight lower bounds for Euclidean spanners. In: FOCS, pp. 519\u2013528 (2008)"},{"issue":"1","key":"9779_CR12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/090776147","volume":"25","author":"M. Elkin","year":"2011","unstructured":"Elkin, M., Solomon, S.: Narrow-shallow-low-light trees with and without steiner points. SIAM J. Discrete Math. 25(1), 181\u2013210 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"9779_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M., Solomon, S.: Optimal Euclidean spanners: really short, thin and lanky. In: STOC (2013, to appear)","DOI":"10.1145\/2488608.2488691"},{"key":"9779_CR14","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1145\/997817.997848","volume-title":"SoCG","author":"J. Gao","year":"2004","unstructured":"Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. In: SoCG, pp. 190\u2013199 (2004)"},{"key":"9779_CR15","first-page":"478","volume-title":"ESA","author":"L.-A. Gottlieb","year":"2008","unstructured":"Gottlieb, L.-A., Roditty, L.: An optimal dynamic spanner for doubling metric spaces. In: ESA, pp. 478\u2013489 (2008)"},{"key":"9779_CR16","first-page":"534","volume-title":"FOCS","author":"A. Gupta","year":"2003","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS, pp. 534\u2013543 (2003)"},{"key":"9779_CR17","first-page":"150","volume-title":"Symposium on Computational Geometry","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: Symposium on Computational Geometry, pp. 150\u2013158 (2005)"},{"key":"9779_CR18","first-page":"186","volume-title":"STOC","author":"C. Levcopoulos","year":"1998","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.H.M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: STOC, pp. 186\u2013195 (1998)"},{"key":"9779_CR19","first-page":"193","volume-title":"WADS","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New results of fault tolerant geometric spanners. In: WADS, pp. 193\u2013204 (1999)"},{"key":"9779_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.H.M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"key":"9779_CR21","unstructured":"Solomon, S.: Fault-tolerant spanners for doubling metrics: better and simpler (2012). arXiv:1207.7040 [cs.Os]"},{"key":"9779_CR22","first-page":"48","volume-title":"ESA (1)","author":"S. Solomon","year":"2010","unstructured":"Solomon, S., Elkin, M.: Balancing degree, diameter and weight in Euclidean spanners. In: ESA (1), pp. 48\u201359 (2010)"},{"issue":"2","key":"9779_CR23","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9779-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9779-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9779-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T05:01:38Z","timestamp":1688187698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9779-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9779"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9779-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}