{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:47Z","timestamp":1725543467221},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_24","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"242-254","source":"Crossref","is-referenced-by-count":2,"title":["Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles"],"prefix":"10.1007","author":[{"given":"Matthias","family":"M\u00fcller-Hannemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Schulze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"http:\/\/www.xinitiative.org"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/505348.505355","volume-title":"SLIP 2002: Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction","author":"S.L. Teig","year":"2002","unstructured":"Teig, S.L.: The X architecture: not your father\u2019s diagonal wiring. In: SLIP 2002: Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction, pp. 33\u201337. ACM Press, New York (2002)"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/639929.639944","volume-title":"Proceedings of SLIP 2003","author":"H. Chen","year":"2003","unstructured":"Chen, H., Cheng, C.K., Kahng, A.B., M\u01cendoiu, I., Wang, Q.: Estimation of wirelength reduction for \u03bb-geometry vs. Manhattan placement and routing. In: Proceedings of SLIP 2003, pp. 71\u201376. ACM Press, New York (2003)"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Paluszewski, M., Winter, P., Zachariasen, M.: A new paradigm for general architecture routing. In: Proceedings of the 14th ACM Great Lakes Symposium on VLSI (GLSVLSI), pp. 202\u2013207 (2004)","DOI":"10.1145\/988952.989002"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics\u00a032, 835\u2013859 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/11602613_27","volume-title":"Algorithms and Computation","author":"M. M\u00fcller-Hannemann","year":"2005","unstructured":"M\u00fcller-Hannemann, M., Schulze, A.: Hardness and approximation of octilinear Steiner trees. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 256\u2013265. Springer, Heidelberg (2005)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1007\/3-540-45749-6_66","volume-title":"Algorithms - ESA 2002","author":"B.K. Nielsen","year":"2002","unstructured":"Nielsen, B.K., Winter, P., Zachariasen, M.: An exact algorithm for the uniformly-oriented Steiner tree problem. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 760\u2013772. Springer, Heidelberg (2002)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Coulston, C.: Constructing exact octagonal Steiner minimal trees. In: ACM Great Lakes Symposium on VLSI, pp. 1\u20136 (2003)","DOI":"10.1145\/764808.764810"},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-48518-X_17","volume-title":"Algorithm Engineering and Experimentation","author":"M. Zachariasen","year":"1999","unstructured":"Zachariasen, M., Winter, P.: Obstacle-avoiding Euclidean Steiner trees in the plane: An exact approach. In: Goodrich, M.T., McGeoch, C.C. (eds.) ALENEX 1999. LNCS, vol.\u00a01619, pp. 282\u2013295. Springer, Heidelberg (1999)"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Althaus, E., Polzin, T., Daneshmand, S.V.: Improving linear programming approaches for the Steiner tree problem. Research Report MPI-I-2003-1-004, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (2003)","DOI":"10.1007\/3-540-44867-5_1"},{"key":"24_CR12","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770\u2013779 (2000)"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/0221059","volume":"21","author":"D.Z. Du","year":"1992","unstructured":"Du, D.Z., Hwang, F.K.: Reducing the Steiner problem in a normed space. SIAM Journal on Computing\u00a021, 1001\u20131007 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BFb0009506","volume-title":"Algorithms and Computation","author":"D.T. Lee","year":"1996","unstructured":"Lee, D.T., Shen, C.F.: The Steiner minimal tree problem in the \u03bb-geometry plane. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 247\u2013255. Springer, Heidelberg (1996)"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/1097-0037(200007)35:4<287::AID-NET8>3.0.CO;2-R","volume":"35","author":"G.H. Lin","year":"2000","unstructured":"Lin, G.H., Xue, G.: Reducing the Steiner problem in four uniform orientations. Networks\u00a035, 287\u2013301 (2000)","journal-title":"Networks"},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for the Euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045, 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing\u00a028, 1298\u20131309 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Kahng, A.B., M\u01cendoiu, I.I., Zelikovsky, A.Z.: Highly scalable algorithms for rectilinear and octilinear Steiner trees. In: Proceedings 2003 Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 827\u2013833 (2003)","DOI":"10.1145\/1119772.1119955"},{"key":"24_CR19","unstructured":"Zhu, Q., Zhou, H., Jing, T., Hong, X., Yang, Y.: Efficient octilinear Steiner tree construction based on spanning graphs. In: Proceedings 2004 Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 687\u2013690 (2004)"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-540-45078-8_19","volume-title":"Algorithms and Data Structures","author":"M. M\u00fcller-Hannemann","year":"2003","unstructured":"M\u00fcller-Hannemann, M., Peyer, S.: Approximation of rectilinear Steiner trees with length restrictions on obstacles. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 207\u2013218. Springer, Heidelberg (2003)"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters\u00a027, 125\u2013128 (1988)","journal-title":"Information Processing Letters"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"J.S.B. Mitchell","year":"2000","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, Amsterdam (2000)"},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(96)80467-7","volume":"70","author":"D.T. Lee","year":"1996","unstructured":"Lee, D.T., Yang, C.D., Wong, C.K.: Rectilinear paths among rectilinear obstacles. Discrete Applied Mathematics\u00a070, 185\u2013215 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Wu, Y.F., Widmayer, P., Schlag, M.D.F., Wong, C.K.: Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computing, 321\u2013331 (1987)","DOI":"10.1109\/TC.1987.1676904"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Kapoor, S., Vaidya, P.M.: Rectilinear shortest paths through polygonal obstacles in O(n (logn)2) time. In: Proceedings of the 3rd Annual ACM Symposium on Computational Geometry, pp. 251\u2013257 (1987)","DOI":"10.1145\/41958.41985"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:18Z","timestamp":1619507958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11785293_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}