{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:36:06Z","timestamp":1725564966238},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228561"},{"type":"electronic","value":"9783540277989"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27798-9_30","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T19:01:28Z","timestamp":1283713288000},"page":"268-277","source":"Crossref","is-referenced-by-count":4,"title":["The Traveling Salesman Problem with Few Inner Points"],"prefix":"10.1007","author":[{"given":"Vladimir G.","family":"Deineko","sequence":"first","affiliation":[]},{"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","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 Euclidean TSP and other geometric problems. J. ACM\u00a045, 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"E. Balas","year":"1989","unstructured":"Balas, E.: The prize collecting traveling salesman problem. Networks\u00a019, 621\u2013636 (1989)","journal-title":"Networks"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R. Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the traveling salesman problem. J. ACM\u00a09, 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"30_CR4","volume-title":"Introduction to algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"30_CR5","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(96)00125-1","volume":"59","author":"V. De\u012dneko","year":"1996","unstructured":"De\u012dneko, V., van Dal, R., Rote, G.: The convex-hull-and-line traveling salesman problem: a solvable case. Inf. Process. Lett.\u00a059, 295\u2013301 (1996)","journal-title":"Inf. Process. Lett."},{"key":"30_CR6","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0020-0190(96)00125-1","volume":"59","author":"V. De\u012dneko","year":"1996","unstructured":"De\u012dneko, V., Woeginger, G.J.: The convex-hull-and-k-line traveling salesman problem. Inf. Process. Lett.\u00a059, 295\u2013301(1996)","journal-title":"Inf. Process. Lett."},{"key":"30_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/opre.4.1.61","volume":"4","author":"M.M. Flood","year":"1956","unstructured":"Flood, M.M.: Traveling salesman problem. Oper. Res.\u00a04, 61\u201375 (1956)","journal-title":"Oper. Res."},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. 8th STOC, pp. 10\u201322 (1976)","DOI":"10.1145\/800113.803626"},{"key":"30_CR10","first-page":"196","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. SIAM\u00a010, 196\u2013210 (1962)","journal-title":"J. SIAM"},{"key":"30_CR11","unstructured":"Hoffmann, M., Okamoto, Y.: The minimum weight triangulation problem with few inner points (submitted)"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/BF01228511","volume":"9","author":"R.Z. Hwang","year":"1993","unstructured":"Hwang, R.Z., Chang, R.C., Lee, R.C.T.: The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica\u00a09, 398\u2013423 (1993)","journal-title":"Algorithmica"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J. Mitchell","year":"1999","unstructured":"Mitchell, J.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial- time approximation scheme for geometric k-MST, TSP, and related problems. SIAM J. Comput.\u00a028, 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"30_CR14","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Habilitation Thesis, Universit\u00e4t T\u00fcbingen (2002)"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theor. Comput. Sci.\u00a04, 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Rao, S., Smith, W.: Approximating geometric graphs via spanners and banyans. In: Proc. 30th STOC, pp. 540\u2013550 (1998)","DOI":"10.1145\/276698.276868"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R. Sedgewick","year":"1977","unstructured":"Sedgewick, R.: Permutation generation methods. ACM Comput. Surveys\u00a09, 137\u2013164 (1977)","journal-title":"ACM Comput. Surveys"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27798-9_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:12Z","timestamp":1605741672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27798-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228561","9783540277989"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27798-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}