{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T07:12:44Z","timestamp":1742800364567},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,7,30]],"date-time":"2011-07-30T00:00:00Z","timestamp":1311984000000},"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":[[2011,12]]},"DOI":"10.1007\/s00453-011-9553-y","type":"journal-article","created":{"date-parts":[[2011,7,29]],"date-time":"2011-07-29T16:10:33Z","timestamp":1311955833000},"page":"924-948","source":"Crossref","is-referenced-by-count":10,"title":["Exact Algorithms for the Bottleneck Steiner Tree Problem"],"prefix":"10.1007","volume":"61","author":[{"given":"Sang Won","family":"Bae","sequence":"first","affiliation":[]},{"given":"Sunghee","family":"Choi","sequence":"additional","affiliation":[]},{"given":"Chunseok","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Shin-ichi","family":"Tanigawa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,30]]},"reference":[{"key":"9553_CR1","unstructured":"Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacrist\u00e1n, V.: The farthest color Voronoi diagram and related problems. Technical report 002, Rheinische Friedrich\u2013Wilhelms\u2013Universit\u00e4t Bonn (2006)"},{"key":"9553_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Komlos, J., Szemeredi, E.: An O(nlog\u2009n) sorting network. Combinatorica 3, 1\u201319 (1983)","journal-title":"Combinatorica"},{"issue":"7","key":"9553_CR3","first-page":"333","volume":"5","author":"A. Ayad","year":"2010","unstructured":"Ayad, A.: A survey on the complexity of solving algebraic systems. Int. Math. Forum 5(7), 333\u2013353 (2010)","journal-title":"Int. Math. Forum"},{"issue":"16","key":"9553_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(16), 672\u2013678 (2010)","journal-title":"Inf. Process. Lett."},{"key":"9553_CR5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/220279.220302","volume-title":"Proceedings of the 11th Annual Symposium on Computational Geometry","author":"I.J. Balaban","year":"1995","unstructured":"Balaban, I.J.: An optimal algorithm for finding segments intersections. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp. 211\u2013219. ACM, New York (1995)"},{"key":"9553_CR6","volume-title":"Research Problems in Discrete Geometry","author":"P. Brass","year":"2005","unstructured":"Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, Berlin (2005)"},{"key":"9553_CR7","first-page":"2","volume-title":"Proceedings of IEEE International Conference on CAD","author":"C. Chiang","year":"1989","unstructured":"Chiang, C., Sarrafzadeh, M., Wong, C.K.: A powerful global router: based on Steiner min-max trees. In: Proceedings of IEEE International Conference on CAD, pp. 2\u20135 (1989)"},{"issue":"1","key":"9553_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1), 200\u2013208 (1987)","journal-title":"J. ACM"},{"key":"9553_CR9","series-title":"Algorithms and Computation in Mathematics","volume-title":"Solving Polynomial Equations: Foundations, Algorithms, and Applications","author":"A. Dickenstein","year":"2005","unstructured":"Dickenstein, A., Emiris, I.Z.: Solving Polynomial Equations: Foundations, Algorithms, and Applications. Algorithms and Computation in Mathematics, vol. 14. Springer, Berlin (2005)"},{"key":"9553_CR10","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/trsc.10.4.321","volume":"10","author":"J. Elzinga","year":"1976","unstructured":"Elzinga, J., Hearn, D., Randolph, W.D.: Minimax multifacility location with Euclidean distances. Transp. Sci. 10, 321\u2013336 (1976)","journal-title":"Transp. Sci."},{"issue":"4","key":"9553_CR11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1006\/jsco.1993.1051","volume":"16","author":"J. Faug\u00e8re","year":"1993","unstructured":"Faug\u00e8re, J., Gianni, P., Lazard, D., Mora, F.: Efficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering. J. Symb. Comput. 16(4), 329\u2013344 (1993)","journal-title":"J. Symb. Comput."},{"key":"9553_CR12","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0167-6377(96)00028-4","volume":"19","author":"J.L. Ganley","year":"1996","unstructured":"Ganley, J.L., Salowe, J.S.: Optimal and approximate bottleneck Steiner trees. Oper. Res. Lett. 19, 217\u2013224 (1996)","journal-title":"Oper. Res. Lett."},{"key":"9553_CR13","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"D.P. Huttenlocher","year":"1993","unstructured":"Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom. 9, 267\u2013291 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9553_CR14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1(1), 59\u201371 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9553_CR15","series-title":"Progress in Mathematics","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-1-4612-0441-1_15","volume-title":"Effective Methods in Algebraic Geometry","author":"Y.N. Lakshman","year":"1991","unstructured":"Lakshman, Y.N.: A single exponential bound on the complexity of computing Gr\u00f6bner bases of zero dimensional ideals. In: Effective Methods in Algebraic Geometry. Progress in Mathematics, vol. 94, pp. 227\u2013234. Birkh\u00e4user, Basel (1991)"},{"issue":"6","key":"9553_CR16","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":"9553_CR17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1080\/00207547308929944","volume":"11","author":"R.F. Love","year":"1973","unstructured":"Love, R.F., Wesolowsky, G.O., Kraemer, S.A.: A multifacility minimax location problem with Euclidean distances. Int. J. Prod. Res. 11, 37\u201345 (1973)","journal-title":"Int. J. Prod. Res."},{"issue":"4","key":"9553_CR18","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852\u2013865 (1983)","journal-title":"J. ACM"},{"key":"9553_CR19","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"9553_CR20","first-page":"742","volume":"27","author":"H. Pr\u00fcfer","year":"1918","unstructured":"Pr\u00fcfer, H.: Neuer Beweis eines Satzes \u00fcber Permutationen. Arch. Math. Phys. 27, 742\u2013744 (1918)","journal-title":"Arch. Math. Phys."},{"key":"9553_CR21","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s002000050114","volume":"9","author":"F. Rouillier","year":"1999","unstructured":"Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Appl. Algebra Eng. Commun. Comput. 9, 433\u2013461 (1999)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"3","key":"9553_CR22","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1109\/12.127452","volume":"41","author":"M. Sarrafzadeh","year":"1992","unstructured":"Sarrafzadeh, M., Wong, C.K.: Bottleneck Steiner trees in the plane. IEEE Trans. Comput. 41(3), 370\u2013374 (1992)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"9553_CR23","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/S0097539794270881","volume":"26","author":"A. Shioura","year":"1997","unstructured":"Shioura, A., Tamura, A., Uno, T.: An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J. Comput. 26(3), 678\u2013692 (1997)","journal-title":"SIAM J. Comput."},{"key":"9553_CR24","volume-title":"Enumerative Combinatorics: Volume 2","author":"R.P. Stanley","year":"2001","unstructured":"Stanley, R.P.: Enumerative Combinatorics: Volume 2. Cambridge University Press, Cambridge (2001)"},{"issue":"2\u20133","key":"9553_CR25","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.comgeo.2004.03.006","volume":"28","author":"R. Oostrum van","year":"2004","unstructured":"van\u00a0Oostrum, R., Veltkamp, R.C.: Parametric search made practical. Comput. Geom. Theory Appl. 28(2\u20133), 75\u201388 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9553_CR26","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":"9553_CR27","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.: An 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."},{"key":"9553_CR28","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-1-4757-3171-2_6","volume-title":"Advances in Steiner Trees","author":"D.M. Warme","year":"2000","unstructured":"Warme, D.M., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: a computational study. In: Du, D.Z., Smith, J.M., Rubinstein, J.H. (eds.) Advances in Steiner Trees, pp. 81\u2013116. Kluwer Academic, Norwell (2000)"},{"key":"9553_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/S0024609397003408","volume":"30","author":"C. Zong","year":"1998","unstructured":"Zong, C.: The kissing numbers of convex bodies\u2014a brief survey. Bull. Lond. Math. Soc. 30, 1\u201330 (1998)","journal-title":"Bull. Lond. Math. Soc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9553-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9553-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9553-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T12:59:19Z","timestamp":1686229159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9553-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,30]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9553"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9553-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,30]]}}}