{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:31:43Z","timestamp":1725550303289},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540304678"},{"type":"electronic","value":"9783540320890"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11589440_11","type":"book-chapter","created":{"date-parts":[[2005,11,9]],"date-time":"2005-11-09T07:08:15Z","timestamp":1131520095000},"page":"106-116","source":"Crossref","is-referenced-by-count":0,"title":["I\/O-Efficiently Pruning Dense Spanners"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[]},{"given":"Jan","family":"Vahrenhold","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"9","key":"11_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"key":"11_CR2","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 & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"11_CR3","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1109\/TPDS.2003.1195412","volume":"14","author":"K.M. Alzoubi","year":"2003","unstructured":"Alzoubi, K.M., Li, X.-Y., Wang, Y., Wan, P.-J., Frieder, O.: Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems\u00a014(4), 408\u2013421 (2003)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-1-4615-0005-6_9","volume-title":"Handbook of Massive Data Sets","author":"L.A. Arge","year":"2002","unstructured":"Arge, L.A.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313\u2013357. Kluwer, Dordrecht (2002)"},{"key":"11_CR5","unstructured":"Arge, L.A., Procopiuc, O., Ramaswamy, S., Suel, T., Vitter, J.S.: Theory and practice of I\/O-efficient algorithms for multidimensional batched searching problems. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 685\u2013694 (1998)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proc. 27th ACM Symposium on Theory of Computing, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proc. 35th IEEE Symposium on Foundations of Computer Science, pp. 703\u2013712 (1994)","DOI":"10.1109\/SFCS.1994.365722"},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.comgeo.2004.01.003","volume":"28","author":"P. Bose","year":"2004","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Computational Geometry: Theory and Applications\u00a028, 11\u201318 (2004)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"11_CR9","unstructured":"Buchsbaum, A.L., Westbrook, J.R.: Maintaining hierarchical graph views. In: Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 566\u2013575 (2000)"},{"key":"11_CR10","unstructured":"Callahan, P.B.: Dealing with higher dimensions: the well-separated pair decomposition and its applications. Ph.D. thesis, Department of Computer Science, Johns Hopkins University, Baltimore, Maryland (1995)"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM\u00a042, 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"key":"11_CR12","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B. Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. International Journal of Computational Geometry and Applications\u00a05, 124\u2013144 (1995)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0166-218X(00)00280-8","volume":"110","author":"D.Z. Chen","year":"2001","unstructured":"Chen, D.Z., Das, G., Smid, M.: Lower bounds for computing geometric spanners and approximate shortest paths. Discrete Applied Mathematics\u00a0110, 151\u2013167 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR14","unstructured":"Chiang, Y.-J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 139\u2013149 (1995)"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: Proc. 9th Annual ACM Symposium on Computational Geometry, pp. 53\u201362 (1993)","DOI":"10.1145\/160985.160998"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G. Das","year":"1997","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. International Journal of Computational Geometry & Applications\u00a07, 297\u2013315 (1997)","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"11_CR17","unstructured":"Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 215\u2013222 (1995)"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425\u2013461. Elsevier Science Publishers, Amsterdam (2000)"},{"key":"11_CR19","unstructured":"Eubank, S., Kumar, V.A., Marathe, M.V., Srinivasany, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: Munro, J.I. (ed.) Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 718\u2013727 (2004)"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/3-540-45253-2_21","volume-title":"Algorithms - ESA 2000","author":"S. Govindarajan","year":"2000","unstructured":"Govindarajan, S., Lukovszki, T., Maheswari, A., Zeh, N.: I\/O-efficient well-separated pair decomposition and its application. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 220\u2013231. Springer, Heidelberg (2000)"},{"issue":"5","key":"11_CR21","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. SIAM Journal of Computing\u00a031(5), 1479\u20131500 (2002)","journal-title":"SIAM Journal of Computing"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graph. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828\u2013837 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/3-540-36574-5_4","volume-title":"Algorithms for Memory Hierarchies","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Meyer, U., Sanders, P., Sibeyn, J.F. (eds.) Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625, pp. 62\u201384. Springer, Heidelberg (2003)"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: Proc. 1st Scandinavian Workshop on Algorithmic Theory, pp. 208\u2013213 (1988)","DOI":"10.1007\/3-540-19487-8_23"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C. Levcopoulos","year":"2002","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica\u00a032, 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"11_CR26","volume-title":"Ad Hoc wireless networking","author":"X.-Y. Li","year":"2003","unstructured":"Li, X.-Y.: Applications of computational geometry in wireless ad hoc networks. In: Cheng, X.-Z., Huang, X., Du, D.-Z. (eds.) Ad Hoc wireless networking. Kluwer, Dordrecht (2003)"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-45294-X_21","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"T. Lukovszki","year":"2001","unstructured":"Lukovszki, T., Maheshwari, A., Zeh, N.: I\/O-efficient batched range counting and its applications to proximity problems. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 244\u2013255. Springer, Heidelberg (2001)"},{"key":"11_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/3-540-44634-6_27","volume-title":"Algorithms and Data Structures","author":"A. Maheshwari","year":"2001","unstructured":"Maheshwari, A., Smid, M., Zeh, N.: I\/O-efficient shortest path queries in geometric spanners. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, pp. 287\u2013299. Springer, Heidelberg (2001)"},{"key":"11_CR29","unstructured":"Navarro, G., Paredes, R.: Practical construction of metric t-spanners. In: 5th Workshop on Algorithmic Engineering and Experiments, pp. 69\u201381. SIMA Press (2003)"},{"key":"11_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/3-540-45735-6_26","volume-title":"String Processing and Information Retrieval","author":"G. Navarro","year":"2002","unstructured":"Navarro, G., Paredes, R., Ch\u00e1vez, E.: t-spanners as a data structure for metric space searching. In: Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. LNCS, vol.\u00a02476, pp. 298\u2013309. Springer, Heidelberg (2002)"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S0218195991000098","volume":"1","author":"J.S. Salowe","year":"1991","unstructured":"Salowe, J.S.: Constructing multidimensional spanner graphs. International Journal of Computational Geometry & Applications\u00a01, 99\u2013107 (1991)","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"11_CR32","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1016\/B978-044482537-7\/50021-8","volume-title":"Handbook of Computational Geometry","author":"M. Smid","year":"2000","unstructured":"Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 877\u2013935. Elsevier Science Publishers, Amsterdam (2000)"},{"key":"11_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-36574-5_5","volume-title":"Algorithms for Memory Hierarchies","author":"L.I. Toma","year":"2003","unstructured":"Toma, L.I., Zeh, N.: I\/O-efficient algorithms for sparse graphs. In: Meyer, U., Sanders, P., Sibeyn, J.F. (eds.) Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625, pp. 85\u2013109. Springer, Heidelberg (2003)"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02574695","volume":"6","author":"P.M. Vaidya","year":"1991","unstructured":"Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete & Computational Geometry\u00a06, 369\u2013381 (1991)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"11_CR35","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys\u00a033(2), 209\u2013271 (2001)","journal-title":"ACM Computing Surveys"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11589440_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:01:33Z","timestamp":1605625293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11589440_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304678","9783540320890"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/11589440_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}