{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:28Z","timestamp":1770994108414,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T00:00:00Z","timestamp":1366243200000},"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":[[2015,1]]},"DOI":"10.1007\/s00453-013-9778-z","type":"journal-article","created":{"date-parts":[[2013,4,17]],"date-time":"2013-04-17T15:51:24Z","timestamp":1366213884000},"page":"36-52","source":"Crossref","is-referenced-by-count":4,"title":["Approximating Minimum Manhattan Networks in Higher Dimensions"],"prefix":"10.1007","volume":"71","author":[{"given":"Aparna","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emden R.","family":"Gansner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,18]]},"reference":[{"issue":"1\u20132","key":"9778_CR1","doi-asserted-by":"crossref","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. 97(1\u20132), 43\u201369 (2003). doi: 10.1007\/s10107-003-0438-y","journal-title":"Math. Program."},{"key":"9778_CR2","first-page":"489","volume-title":"Proc. 27th Annu. ACM Sympos. Theory Comput. (STOC\u201995)","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 Sympos. Theory Comput. (STOC\u201995), pp. 489\u2013498 (1995). doi: 10.1145\/225058.225191"},{"issue":"3","key":"9778_CR3","doi-asserted-by":"crossref","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. 35(3), 188\u2013208 (2006). doi: 10.1016\/j.comgeo.2005.09.004","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"9778_CR4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999). doi: 10.1006\/jagm.1999.1042","journal-title":"J. Algorithms"},{"issue":"1","key":"9778_CR5","doi-asserted-by":"crossref","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. 390(1), 56\u201369 (2008). doi: 10.1016\/j.tcs.2007.10.013","journal-title":"Theor. Comput. Sci."},{"key":"9778_CR6","doi-asserted-by":"crossref","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. 45, 701\u2013722 (2011). doi: 10.1007\/s00454-011-9342-z","journal-title":"Discrete Comput. Geom."},{"key":"9778_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 arXiv:1107.0901v2 (2011)","DOI":"10.1007\/978-3-642-23719-5_5"},{"issue":"1","key":"9778_CR8","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.jcss.2011.05.009","volume":"78","author":"M. Feldman","year":"2012","unstructured":"Feldman, M., Kortsarz, G., Nutov, Z.: Improved approximating algorithms for directed Steiner forest. J. Comput. Syst. Sci. 78(1), 279\u2013292 (2012). doi: 10.1016\/j.jcss.2011.05.009","journal-title":"J. Comput. Syst. Sci."},{"key":"9778_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). See http:\/\/e-archive.informatik.uni-koeln.de\/570"},{"key":"9778_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. 8, 219\u2013232 (2001). See http:\/\/www.cs.helsinki.fi\/njc\/References\/gudmundssonln:219.html","journal-title":"Nordic J. Comput."},{"issue":"3","key":"9778_CR11","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1142\/S0218195911003688","volume":"21","author":"Z. Guo","year":"2011","unstructured":"Guo, Z., Sun, H., Zhu, H.: Greedy construction of 2-approximate minimum Manhattan networks. Int. J. Comput. Geom. Appl. 21(3), 331\u2013350 (2011). doi: 10.1142\/S0218195911003688","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9778_CR12","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/3-540-36136-7_31","volume-title":"Proc. 13th Annu. Internat. Sympos. Algorithms Comput. (ISAAC\u201902)","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.) Proc. 13th Annu. Internat. Sympos. Algorithms Comput. (ISAAC\u201902). Lecture Notes Comput. Sci., vol. 2518, pp. 344\u2013356. Springer, Berlin (2002). doi: 10.1007\/3-540-36136-7_31"},{"key":"9778_CR13","doi-asserted-by":"crossref","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. 10, 509\u2013520 (2003). doi: 10.1089\/10665270360688156","journal-title":"J. Comput. Biol."},{"issue":"3","key":"9778_CR14","doi-asserted-by":"crossref","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. 4(3), 357\u2013363 (2000). doi: 10.1023\/A:1009826311973","journal-title":"J. Comb. Optim."},{"key":"9778_CR15","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/978-3-642-00202-1_32","volume-title":"Proc. 3rd Internat. Workshop Algorithms Comput. (WALCOM\u201909)","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.) Proc. 3rd Internat. Workshop Algorithms Comput. (WALCOM\u201909). Lecture Notes Comput. Sci., vol. 5431, pp. 369\u2013380. Springer, Berlin (2009). doi: 10.1007\/978-3-642-00202-1_32"},{"key":"9778_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). See http:\/\/www.lif-sud.univ-mrs.fr\/~karim\/download\/THESE_NOUIOUA.pdf"},{"key":"9778_CR17","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/11602613_26","volume-title":"Proc. 16th Intern. Symp. Algorithms Comput. (ISAAC\u201905)","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.) Proc. 16th Intern. Symp. Algorithms Comput. (ISAAC\u201905). Lecture Notes Comput. Sci., vol. 3827, pp. 246\u2013255. Springer, Berlin (2005). doi: 10.1007\/11602613_26"},{"key":"9778_CR18","series-title":"Lecture Notes Comput. Sci.","first-page":"389","volume-title":"Proc. 16th Internat. Conf. Integer Prog. Comb. Optimization (IPCO\u201911)","author":"J.A. Soto","year":"2011","unstructured":"Soto, J.A., Telha, C.: Jump number of two-directional orthogonal ray graphs. In: G\u00fcnl\u00fck, O., Woeginger, G. (eds.) Proc. 16th Internat. Conf. Integer Prog. Comb. Optimization (IPCO\u201911). Lecture Notes Comput. Sci., vol. 6655, pp. 389\u2013403. Springer, Berlin (2011). doi: 10.1007\/978-3-642-20807-2_31"},{"issue":"1","key":"9778_CR19","doi-asserted-by":"crossref","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 18(1), 99\u2013110 (1997). doi: 10.1007\/BF02523690","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9778-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9778-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9778-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:06:16Z","timestamp":1562958376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9778-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,18]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9778"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9778-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,18]]}}}