{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:40:59Z","timestamp":1771026059013,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T00:00:00Z","timestamp":1384214400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00454-013-9550-9","type":"journal-article","created":{"date-parts":[[2013,11,11]],"date-time":"2013-11-11T09:42:36Z","timestamp":1384162956000},"page":"1-23","source":"Crossref","is-referenced-by-count":7,"title":["The Euclidean Bottleneck Steiner Path Problem and Other Applications of (\u03b1,\u03b2)-Pair Decomposition"],"prefix":"10.1007","volume":"51","author":[{"given":"A. Karim","family":"Abu-Affash","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paz","family":"Carmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Segal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,12]]},"reference":[{"issue":"5\u20136","key":"9550_CR1","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.comgeo.2011.12.003","volume":"45","author":"M.A. Abam","year":"2012","unstructured":"Abam, M.A., Har-Peled, S.: New constructions of SSPDs and their applications. Comput. Geom. 45(5\u20136), 200\u2013214 (2012)","journal-title":"Comput. Geom."},{"issue":"4","key":"9550_CR2","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/s00454-009-9137-7","volume":"41","author":"M.A. Abam","year":"2009","unstructured":"Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete Comput. Geom. 41(4), 556\u2013582 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9550_CR3","first-page":"81","volume-title":"Proceedings of the 8th International Conference on Principles of Distributed Systems","author":"F. Ara\u00fajo","year":"2004","unstructured":"Ara\u00fajo, F., Rodrigues, L.: Fast localized Delaunay triangulation. In: Proceedings of the 8th International Conference on Principles of Distributed Systems, pp. 81\u201393 (2004)"},{"key":"9550_CR4","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/j.ipl.2010.05.014","volume":"110","author":"S.W. Bae","year":"2010","unstructured":"Bae, S.W., Lee, C., Choi, S.: On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf. Process. Lett. 110, 672\u2013678 (2010)","journal-title":"Inf. Process. Lett."},{"key":"9550_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-001-0114-7","volume":"33","author":"S. Bespamyatnikh","year":"2002","unstructured":"Bespamyatnikh, S., Segal, M.: Fast algorithms for approximating distances. Algorithmica 33, 263\u2013269 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"9550_CR6","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1016\/j.ejc.2006.04.003","volume":"28","author":"B. Bollob\u00e1s","year":"2007","unstructured":"Bollob\u00e1s, B., Scott, A.: On separating systems. Eur. J. Comb. 28(4), 1068\u20131071 (2007)","journal-title":"Eur. J. Comb."},{"key":"9550_CR7","first-page":"282","volume-title":"Proceedings LATIN","author":"P. Bose","year":"2010","unstructured":"Bose, P., Carmi, P., Smid, M., Xu, D.: Communication-efficient construction of the plane localized Delaunay graph. In: Proceedings LATIN, pp. 282\u2013293 (2010)"},{"key":"9550_CR8","doi-asserted-by":"crossref","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. J. ACM 42, 67\u201390 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"9550_CR9","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1142\/S0218195901000511","volume":"11","author":"T. Chan","year":"2001","unstructured":"Chan, T.: On enumerating and selecting distances. Int. J. Comput. Geom. Appl. 11(3), 291\u2013304 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9550_CR10","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1023\/A:1008384012064","volume":"18","author":"D. Chen","year":"2000","unstructured":"Chen, D., Du, D.-Z., Hu, X., Lin, G., Wang, L., Xue, G.: Approximations for Steiner trees with minimum number of Steiner points. J. Glob. Optim. 18, 17\u201333 (2000)","journal-title":"J. Glob. Optim."},{"key":"9550_CR11","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11276-006-0724-8","volume":"14","author":"X. Cheng","year":"2008","unstructured":"Cheng, X., Du, D.-Z., Wang, L., Xu, B.: Relay sensor placement in wireless sensor networks. Wirel. Netw. 14, 347\u2013355 (2008)","journal-title":"Wirel. Netw."},{"key":"9550_CR12","first-page":"56","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC \u201987)","author":"K.L. Clarkson","year":"1987","unstructured":"Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC \u201987), pp. 56\u201365 (1987)"},{"key":"9550_CR13","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9550_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)"},{"key":"9550_CR15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: sorted matrices. SIAM J. Comput. 13, 14\u201330 (1984)","journal-title":"SIAM J. Comput."},{"key":"9550_CR16","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1145\/2488608.2488684","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC \u201913)","author":"S. Har-Peled","year":"2013","unstructured":"Har-Peled, S., Raichel, B.A.: Net and prune: a linear time algorithm for Euclidean distance problems. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC \u201913), pp. 605\u2013614 (2013)"},{"key":"9550_CR17","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1007\/s11276-009-0186-x","volume":"16","author":"Y.-T. Hou","year":"2010","unstructured":"Hou, Y.-T., Chen, C.-M., Jeng, B.: An optimal new-node placement to enhance the coverage of wireless sensor networks. Wirel. Netw. 16, 1033\u20131043 (2010)","journal-title":"Wirel. Netw."},{"issue":"1","key":"9550_CR18","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1023\/B:MONE.0000048542.38105.99","volume":"10","author":"H. Huang","year":"2005","unstructured":"Huang, H., Richa, A.W., Segal, M.: Dynamic coverage in ad-hoc sensor networks. Mob. Netw. Appl. 10(1), 9\u201317 (2005)","journal-title":"Mob. Netw. Appl."},{"issue":"5","key":"9550_CR19","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"M.J. Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26(5), 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"key":"9550_CR20","series-title":"LNCS","first-page":"208","volume-title":"Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT \u201988)","author":"J.M. Keil","year":"1988","unstructured":"Keil, J.M.: Approximating the complete Euclidean graph. In: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT \u201988). LNCS, vol. 318, pp. 208\u2013213 (1988)"},{"key":"9550_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511754722","volume-title":"Wireless Ad Hoc and Sensor Networks: Theory and Applications","author":"X.-Y. Li","year":"2008","unstructured":"Li, X.-Y.: Wireless Ad Hoc and Sensor Networks: Theory and Applications. Cambridge University Press, Cambridge (2008)"},{"issue":"10","key":"9550_CR22","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1109\/TPDS.2003.1239871","volume":"14","author":"X.-Y. Li","year":"2003","unstructured":"Li, X.-Y., Calinescu, G., Wan, P.-J., Wang, Y.: Localized Delaunay triangulation with application in ad-hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 14(10), 1035\u20131047 (2003)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"6","key":"9550_CR23","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1007\/BF02973441","volume":"19","author":"Z.-M. Li","year":"2004","unstructured":"Li, Z.-M., Zhu, D.-M., Ma, S.-H.: Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane. J. Comput. Sci. Technol. 19(6), 791\u2013794 (2004)","journal-title":"J. Comput. Sci. Technol."},{"key":"9550_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0020-0190(98)00201-4","volume":"69","author":"G.H. Lin","year":"1999","unstructured":"Lin, G.H., Xue, G.: Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf. Process. Lett. 69, 53\u201357 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9550_CR25","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1109\/TMC.2005.15","volume":"4","author":"S. Megerian","year":"2005","unstructured":"Megerian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Worst and best-case coverage in sensor networks. IEEE Trans. Mob. Comput. 4(1), 84\u201392 (2005)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"9550_CR26","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"key":"9550_CR27","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s00453-009-9322-3","volume":"59","author":"L. Roditty","year":"2011","unstructured":"Roditty, L., Segal, M.: On bounded leg shortest path problems. Algorithmica 59, 583\u2013600 (2011)","journal-title":"Algorithmica"},{"key":"9550_CR28","first-page":"320","volume-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201998)","author":"K.R. Varadarajan","year":"1998","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201998), pp. 320\u2013331 (1998)"},{"key":"9550_CR29","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/s00453-001-0089-4","volume":"32","author":"L. Wang","year":"2002","unstructured":"Wang, L., Du, D.-Z.: Approximations for a bottleneck Steiner tree problem. Algorithmica 32, 554\u2013561 (2002)","journal-title":"Algorithmica"},{"key":"9550_CR30","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0020-0190(01)00209-5","volume":"81","author":"L. Wang","year":"2002","unstructured":"Wang, L., Li, Z.-M.: Approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. Inf. Process. Lett. 81, 151\u2013156 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9550_CR31","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J. Comput. 11(4), 721\u2013736 (1982)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9550-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-013-9550-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9550-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:50:37Z","timestamp":1559073037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-013-9550-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,12]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9550"],"URL":"https:\/\/doi.org\/10.1007\/s00454-013-9550-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,12]]}}}