{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:49Z","timestamp":1725603649252},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_5","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"49-60","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Minimum Manhattan Networks in Higher Dimensions"],"prefix":"10.1007","author":[{"given":"Aparna","family":"Das","sequence":"first","affiliation":[]},{"given":"Emden R.","family":"Gansner","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1\u20132","key":"5_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S. Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Program.\u00a097(1\u20132), 43\u201369 (2003)","journal-title":"Math. Program."},{"key":"5_CR2","first-page":"489","volume-title":"Proc. 27th Annu. ACM Symp. Theory Comput. (STOC)","author":"S. Arya","year":"1995","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: Short, thin, and lanky. In: Proc. 27th Annu. ACM Symp. Theory Comput (STOC), pp. 489\u2013498. ACM Press, New York (1995)"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.comgeo.2005.09.004","volume":"35","author":"M. Benkert","year":"2006","unstructured":"Benkert, M., Wolff, A., Widmann, F., Shirabe, T.: The minimum Manhattan network problem: Approximations and exact solutions. Comput. Geom. Theory Appl.\u00a035(3), 188\u2013208 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"5_CR4","unstructured":"Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. In: Proc. 9th ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 192\u2013200 (1998)"},{"issue":"1","key":"5_CR5","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2007.10.013","volume":"390","author":"V. Chepoi","year":"2008","unstructured":"Chepoi, V., Nouioua, K., Vax\u00e8s, Y.: A rounding algorithm for approximating minimum Manhattan networks. Theor. Comput. Sci.\u00a0390(1), 56\u201369 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/s00454-011-9342-z","volume":"45","author":"F. Chin","year":"2011","unstructured":"Chin, F., Guo, Z., Sun, H.: Minimum Manhattan network is NP-complete. Discrete Comput. Geom.\u00a045, 701\u2013722 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Das, A., Gansner, E.R., Kaufmann, M., Kobourov, S., Spoerhase, J., Wolff, A.: Approximating minimum Manhattan networks in higher dimensions. ArXiv e-print abs\/1107.0901 (2011)","DOI":"10.1007\/978-3-642-23719-5_5"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximating algorithms for directed Steiner forest. In: Proc. 20th ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 922\u2013931 (2009)","DOI":"10.1137\/1.9781611973068.100"},{"key":"5_CR9","unstructured":"Fuchs, B., Schulze, A.: A simple 3-approximation of minimum Manhattan networks. Tech. Rep. 570, Zentrum f\u00fcr Angewandte Informatik K\u00f6ln (2008)"},{"key":"5_CR10","first-page":"219","volume":"8","author":"J. Gudmundsson","year":"2001","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Approximating a minimum Manhattan network. Nordic J. Comput.\u00a08, 219\u2013232 (2001)","journal-title":"Nordic J. Comput."},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/978-3-540-92182-0_4","volume-title":"Algorithms and Computation","author":"Z. Guo","year":"2008","unstructured":"Guo, Z., Sun, H., Zhu, H.: Greedy construction of 2-approximation minimum Manhattan network. In: Hong, S., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 4\u201315. Springer, Heidelberg (2008)"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/3-540-36136-7_31","volume-title":"Algorithms and Computation","author":"R. Kato","year":"2002","unstructured":"Kato, R., Imai, K., Asano, T.: An improved algorithm for the minimum Manhattan network problem. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 344\u2013356. Springer, Heidelberg (2002)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1089\/10665270360688156","volume":"10","author":"F. Lam","year":"2003","unstructured":"Lam, F., Alexandersson, M., Pachter, L.: Picking alignments from (Steiner) trees. J. Comput. Biol.\u00a010, 509\u2013520 (2003)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"5_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1009826311973","volume":"4","author":"B. Lu","year":"2000","unstructured":"Lu, B., Ruan, L.: Polynomial time approximation scheme for the rectilinear Steiner arborescence problem. J. Comb. Optim.\u00a04(3), 357\u2013363 (2000)","journal-title":"J. Comb. Optim."},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-00202-1_32","volume-title":"WALCOM: Algorithms and Computation","author":"X. Mu\u00f1oz","year":"2009","unstructured":"Mu\u00f1oz, X., Seibert, S., Unger, W.: The minimal Manhattan network problem in three dimensions. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol.\u00a05431, pp. 369\u2013380. Springer, Heidelberg (2009)"},{"key":"5_CR16","unstructured":"Nouioua, K.: Enveloppes de Pareto et R\u00e9seaux de Manhattan: Caract\u00e9risations et Algorithmes. Ph.D. thesis, Universit\u00e9 de la M\u00e9diterran\u00e9e (2005)"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/11602613_26","volume-title":"Algorithms and Computation","author":"S. Seibert","year":"2005","unstructured":"Seibert, S., Unger, W.: A 1.5-approximation of the minimal Manhattan network problem. In: Deng, X., Du, D. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 246\u2013255. Springer, Heidelberg (2005)"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","first-page":"389","volume-title":"IPCO 2011","author":"J.A. Soto","year":"2011","unstructured":"Soto, J.A., Telha, C.: Jump number of two-directional orthogonal ray graphs. In: G\u00fcl\u00fck, O., Woeginger, G. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 389\u2013403. Springer, Heidelberg (2011)"},{"issue":"1","key":"5_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A. Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica\u00a018(1), 99\u2013110 (1997)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:08:05Z","timestamp":1560514085000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}