{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T05:17:23Z","timestamp":1738387043223,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540688655"},{"type":"electronic","value":"9783540688808"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68880-8_21","type":"book-chapter","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T06:37:59Z","timestamp":1217486279000},"page":"212-223","source":"Crossref","is-referenced-by-count":5,"title":["A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem"],"prefix":"10.1007","author":[{"given":"Zeyu","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"He","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Benkert, M., Wolff, A., Widmann, F.: The minimum Manhattan network problem: a fast factor-3 approximation. Technical Report 2004-16, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe. In: Proceedings of the 8th Japanese Conference on Discrete and Computational Geometry, pp. 16\u201328 (2005) (A sort version appeared)","DOI":"10.1007\/11589440_2"},{"key":"21_CR2","unstructured":"Benkert, M., Shirabe, T., Wolff, A.: The minimum Manhattan network problem: approximations and exact solution. In: Proceedings of the 20th European Workshop on Computational Geometry, pp. 209\u2013212 (2004)"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0377-2217(81)90197-1","volume":"6","author":"G. Chalmet","year":"1981","unstructured":"Chalmet, G., Francis, L., Kolen, A.: Finding efficient solutions for rectilinear distance location problems efficiently. European Journal of Operations Research\u00a06, 117\u2013124 (1981)","journal-title":"European Journal of Operations Research"},{"key":"21_CR4","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. Theoretical Computer Science\u00a0390, 56\u201369 (2008) Preliminary version appeared. In: Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 40\u201351 (2005)","journal-title":"Theoretical Computer Science"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Frances Yao, F.: Efficient dynamic programming using quadrangle inequalities. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 429\u2013435 (1980)","DOI":"10.1145\/800141.804691"},{"key":"21_CR6","first-page":"219","volume":"8","author":"J. Gudmundsson","year":"2001","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Approximating a minimum Manhattan network. Nordic Journal of Computing\u00a08, 219\u2013232 (2001); Preliminary version appeared. In: Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 28\u201337 (1999)","journal-title":"Nordic Journal of Computing"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Kato, R., Imai, K., Asano, T.: An improved algorithm for the minimum Manhattan network problem. In: Proceedings of the 13th International Symposium on Algorithms and Computation, pp. 344\u2013356 (2002)","DOI":"10.1007\/3-540-36136-7_31"},{"key":"21_CR8","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. Journal of Computational Biology\u00a010, 509\u2013520 (2003)","journal-title":"Journal of Computational Biology"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Seibert, S., Unger, W.: A 1.5-approximation of the minimal Manhattan network problem. In: Proceedings of the 16th International Symposium on Algorithms and Computation, pp. 246\u2013255 (2005)","DOI":"10.1007\/11602613_26"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68880-8_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T07:21:24Z","timestamp":1738308084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68880-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688655","9783540688808"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68880-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}