{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:35:44Z","timestamp":1725478544448},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540695134"},{"type":"electronic","value":"9783540695141"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_6","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T00:47:40Z","timestamp":1169599660000},"page":"69-82","source":"Crossref","is-referenced-by-count":3,"title":["On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems"],"prefix":"10.1007","author":[{"given":"Hans","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Corinne","family":"Feremans","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Grigoriev","sequence":"additional","affiliation":[]},{"given":"Eelko","family":"Penninkx","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Wolle","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E.M. Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics\u00a055, 197\u2013218 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/273865.273870","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM\u00a045, 1\u201330 (1998)","journal-title":"Journal of the ACM"},{"key":"6_CR3","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. Mathematical Programming\u00a097, 43\u201369 (2003)","journal-title":"Mathematical Programming"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M. Berg de","year":"2005","unstructured":"de Berg, M., Gudmundsson, J., Katz, M., Levcopoulos, C., Overmars, M., van der Stappen, A.: TSP with neighborhoods of varying size. Journal of Algorithms\u00a057, 22\u201336 (2005)","journal-title":"Journal of Algorithms"},{"key":"6_CR6","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Open problems from CCCG 2000 (2000), \n                  \n                    http:\/\/theory.lcs.mit.edu\/~edemaine\/papers\/CCCG2000Open\/"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A. Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms\u00a048, 135\u2013159 (2003)","journal-title":"Journal of Algorithms"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1007\/11523468_90","volume-title":"Automata, Languages and Programming","author":"K. Elbassioni","year":"2005","unstructured":"Elbassioni, K., Fishkin, A.V., Mustafa, N.H., Sitters, R.: Approximation algorithms for Euclidean group TSP. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1115\u20131126. Springer, Heidelberg (2005)"},{"key":"6_CR10","unstructured":"Feremans, C.: Generalized Spanning Trees and Extensions. PhD thesis, Universit\u00e9 Libre de Bruxelles, Brussels (2001)"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00404-6","volume":"148","author":"C. Feremans","year":"2003","unstructured":"Feremans, C., Labb\u00e9, M., Laporte, G.: Generalized network design problems. European Journal of Operational Research\u00a0148, 1\u201313 (2003)","journal-title":"European Journal of Operational Research"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.45.3.378","volume":"45","author":"M. Fischetti","year":"1997","unstructured":"Fischetti, M., Salazar, J.J., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research\u00a045, 378\u2013394 (1997)","journal-title":"Operations Research"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory\u00a051, 53\u201381 (2006)","journal-title":"Journal of Graph Theory"},{"key":"6_CR14","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 of Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"6_CR15","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/11523468_31","volume-title":"Automata, Languages and Programming","author":"Q. Gu","year":"2005","unstructured":"Gu, Q., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n\n                        3) time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R","volume":"37","author":"C.S. Helvig","year":"2001","unstructured":"Helvig, C.S., Robins, G., Zelikovsky, A.: An improved approximation scheme for the Group Steiner Problem. Networks\u00a037, 8\u201320 (2001)","journal-title":"Networks"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1287\/ijoc.1040.0075","volume":"17","author":"I.V. Hicks","year":"2005","unstructured":"Hicks, I.V.: Planar branch decompositions I: The ratcatcher. Informs Journal on Computing\u00a017, 402\u2013412 (2005)","journal-title":"Informs Journal on Computing"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1287\/ijoc.1040.0074","volume":"17","author":"I.V. Hicks","year":"2005","unstructured":"Hicks, I.V.: Planar branch decompositions II: The cycle method. Informs Journal on Computing\u00a017, 413\u2013421 (2005)","journal-title":"Informs Journal on Computing"},{"issue":"4","key":"6_CR20","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"6_CR22","first-page":"360","volume-title":"ACM SoCG 1995","author":"C.S. Mata","year":"1995","unstructured":"Mata, C.S., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems. In: ACM SoCG 1995, Vancouver, BC, Canada, pp. 360\u2013369. ACM, New York (1995)"},{"key":"6_CR23","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: Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, North-Holland (2000)"},{"key":"6_CR24","first-page":"540","volume-title":"ACM STOC 1998","author":"S. Rao","year":"1998","unstructured":"Rao, S., Smith, W.D.: Approximating geometric graphs via spanners and banyans. In: ACM STOC 1998, Dallas, Texas, USA, pp. 540\u2013550. ACM, New York (1998)"},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-52292-1_14","volume-title":"Graph-Theoretic Concepts in Computer Science, 15th International Workshop, WG 1989","author":"G. Reich","year":"1990","unstructured":"Reich, G., Widmayer, P.: Beyond Steiner\u2019s problem: a VLSI oriented generalization. In: Nagl, M. (ed.) WG 1989. LNCS, vol.\u00a0411, pp. 196\u2013210. Springer, Heidelberg (1990)"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-540-39658-1_41","volume-title":"Algorithms - ESA 2003","author":"S. Safra","year":"2003","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating TSP with neighborhoods and related problems. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 446\u2013458. Springer, Heidelberg (2003)"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"6_CR28","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-002-0326-x","volume":"94","author":"M. Zachariasen","year":"2003","unstructured":"Zachariasen, M., Rohe, A.: Rectilinear group Steiner trees and applications in VLSI design. Mathematical Programming\u00a094, 407\u2013433 (2003)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:23:54Z","timestamp":1619493834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11970125_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}