{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:55:05Z","timestamp":1725854105783},"publisher-location":"New York, NY","reference-count":19,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_426","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T19:32:23Z","timestamp":1553110343000},"page":"2249-2252","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Traveling Sales Person with Few Inner Points"],"prefix":"10.1007","author":[{"given":"Yoshio","family":"Okamoto","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"418_CR20239","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.orl.2005.01.002","volume":"31","author":"VG D\u011bneko","year":"2006","unstructured":"D\u011bneko VG, Hoffmann M, Okamoto Y, Woeginger GJ (2006) The traveling salesman problem with few inner points. Oper Res Lett 31:106\u2013110","journal-title":"Oper Res Lett"},{"key":"418_CR20240","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity. Monographs in computer science","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Monographs in computer science. Springer, New York"},{"key":"418_CR20241","volume-title":"Parameterized complexity theory. Texts in theoretical computer science an EATCS series","author":"J Flum","year":"2006","unstructured":"Flum J, Grohe M (2006) Parameterized complexity theory. Texts in theoretical computer science an EATCS series. Springer, Berlin"},{"key":"418_CR20242","doi-asserted-by":"crossref","unstructured":"Garey MR, Graham RL, Johnson DS (1976) Some NP-complete geometric problems. In: Proceedings of 8th annual ACM  symposium on theory of computing (STOC '76). Association for Computing Machinery, New York, pp 10\u201322","DOI":"10.1145\/800113.803626"},{"key":"418_CR20243","unstructured":"Grantson M (2004) Fixed-parameter algorithms and other results for optimal partitions. Lecentiate thesis, Department of Computer Science, Lund University"},{"key":"418_CR20244","unstructured":"Grantson M, Borgelt C, Levcopoulos C (2005) A fixed parameter algorithm for minimum weight triangulation: analysis and experiments. Technical report 154, Department of Computer Science, Lund University"},{"key":"418_CR20245","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1007\/11602613_98","volume-title":"Proceedings of the 16th annual international symposium on algorithms and computation (ISAAC)","author":"M Grantson","year":"2005","unstructured":"Grantson M, Borgelt C, Levcopoulos C (2005) Minimum weight triangulation by cutting out triangles. In: Deng X, Du D-Z (eds) Proceedings of the 16th annual international symposium on algorithms and computation (ISAAC). Lecture notes in computer science, vol 3827. Springer, New York, pp 984\u2013994"},{"key":"418_CR20246","unstructured":"Grantson M, Borgelt C, Levcopoulos C (2006) Fixed parameter algorithms for the minimum weight triangulation problem. Technical report 158, Department of Computer Science, Lund University"},{"key":"418_CR20247","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/11589440_9","volume-title":"Proceedings of Japanese conference on discrete and computational geometry (JCDCG 2004)","author":"M Grantson","year":"2005","unstructured":"Grantson M, Levcopoulos C (2005) A fixed parameter algorithm for the minimum number convex partition problem. In: Akiyama J, Kano M, Tan X (eds) Proceedings of Japanese conference on discrete and computational geometry (JCDCG 2004). Lecture notes in computer science, vol 3742. Springer, New York, pp 83\u201394"},{"key":"418_CR20248","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.comgeo.2005.11.006","volume":"34","author":"M Hoffmann","year":"2006","unstructured":"Hoffmann M, Okamoto Y (2006) The minimum weight triangulation problem with few inner points. Comput Geom Theor Appl 34:149\u2013158","journal-title":"Comput Geom Theor Appl"},{"key":"418_CR20249","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BF01990536","volume":"33","author":"K Jansen","year":"1993","unstructured":"Jansen K, Woeginger GJ (1993) The complexity of detecting crossingfree configurations in the plane. BIT 33:580\u2013595","journal-title":"BIT"},{"key":"418_CR20250","unstructured":"Knauer C, Spillner A (2006) Fixed-parameter algorithms for finding crossing-free spanning trees in geometric graphs. Technical report 06\u201307, Department of Computer Science, Friedrich-Schiller-Universit\u00e4t Jena"},{"key":"418_CR20251","doi-asserted-by":"crossref","unstructured":"Knauer C, Spillner A (2006) A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators. In: Proceedings of the 32nd international workshop on graph-theoretic concepts in computer science (WG). Lecture notes in computer science, vol 4271. Springer, New York, pp 49\u201357","DOI":"10.1007\/11917496_5"},{"volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","year":"1985","key":"418_CR20252","unstructured":"Lawler E, Lenstra J, Rinnooy Kan A, Shmoys D (eds) (1985) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, Chichester"},{"key":"418_CR20253","unstructured":"Mulzer W, Rote G (2006) Minimum weight triangulation is NP-hard. In: Proceedings of the 22nd annual ACM symposium on computational geometry (SoCG). Association for Computing Machinery, New York, pp 1\u201310"},{"key":"418_CR20254","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications, vol 31. Oxford University Press, Oxford"},{"key":"418_CR20255","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4:237\u2013244","journal-title":"Theor Comput Sci"},{"key":"418_CR20256","first-page":"135","volume-title":"Proceedings of the 1st ACiD workshop. Texts in algorithmics","author":"A Spillner","year":"2005","unstructured":"Spillner A (2005) A faster algorithm for the minimum weight triangulation problem with few inner points. In: Broersma H, Johnson H, Szeider S (eds) Proceedings of the 1st ACiD workshop. Texts in algorithmics, vol 4. King's College, London, pp 135\u2013146"},{"key":"418_CR20257","unstructured":"Spillner A (2005) Optimal convex partitions of point sets with few inner points. In: Proceedings of the 17th Canadian conference on computational geometry (CCCG), pp 34\u201337"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:21:21Z","timestamp":1553113281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_426","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}