{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:45:12Z","timestamp":1743151512093,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":19,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_426","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:37:39Z","timestamp":1214505459000},"page":"961-963","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","reference":[{"key":"426_CR1_426","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.orl.2005.01.002","volume":"31","author":"V.G. De\u012dneko","year":"2006","unstructured":"De\u012dneko, V.G., Hoffmann, M., Okamoto, Y., Woeginger, G.J.: The traveling salesman problem with few inner points. Oper. Res. Lett. 31, 106\u2013110 (2006)","journal-title":"Oper. Res. Lett."},{"key":"426_CR2_426","volume-title":"Monographs in Computer Science","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. In: Monographs in Computer Science. Springer, New York (1999)"},{"key":"426_CR3_426","series-title":"Texts in Theoretical Computer Science An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science An EATCS Series. Springer, Berlin (2006)"},{"key":"426_CR4_426","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/800113.803626","volume-title":"Proceedings of 8th Annual ACM Symposium on Theory of Computing (STOC '76)","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of 8th Annual ACM Symposium on Theory of Computing (STOC '76), pp.\u00a010\u201322. Association for Computing Machinery, New York (1976)"},{"key":"426_CR5_426","unstructured":"Grantson, M.: Fixed\u2010parameter algorithms and other results for optimal partitions. Lecentiate Thesis, Department of Computer Science, Lund University (2004)"},{"key":"426_CR6_426","unstructured":"Grantson, M., Borgelt, C., Levcopoulos, C.: A\u00a0fixed parameter algorithm for minimum weight triangulation: Analysis and experiments. Tech. Rep. 154, Department of Computer Science, Lund University (2005)"},{"key":"426_CR7_426","first-page":"984","volume-title":"Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 3827","author":"M. Grantson","year":"2005","unstructured":"Grantson, M., Borgelt, C., Levcopoulos, C.: Minimum weight triangulation by cutting out triangles. In: Deng, X., Du, D.-Z.\u00a0(eds.) Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol.\u00a03827, pp.\u00a0984\u2013994. Springer, New York (2005)"},{"key":"426_CR8_426","unstructured":"Grantson, M., Borgelt, C., Levcopoulos, C.: Fixed parameter algorithms for the minimum weight triangulation problem. Tech. Rep. 158, Department of Computer Science, Lund University (2006)"},{"key":"426_CR9_426","first-page":"83","volume-title":"Proceedings of Japanese Conference on Discrete and Computational Geometry (JCDCG 2004). Lecture Notes in Computer Science, vol. 3742","author":"M. Grantson","year":"2005","unstructured":"Grantson, M., Levcopoulos, C.: A\u00a0fixed parameter algorithm for the minimum number convex partition problem. In: Akiyama,\u00a0J., Kano, M., Tan, X. (eds.) Proceedings of Japanese Conference on Discrete and Computational Geometry (JCDCG 2004). Lecture Notes in Computer Science, vol.\u00a03742, pp.\u00a083\u201394. Springer, New York (2005)"},{"key":"426_CR10_426","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.: The minimum weight triangulation problem with few inner points. Comput. Geom. Theory Appl. 34, 149\u2013158 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"426_CR11_426","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BF01990536","volume":"33","author":"K. Jansen","year":"1993","unstructured":"Jansen, K., Woeginger, G.J.: The complexity of detecting crossingfree configurations in the plane. BIT 33, 580\u2013595 (1993)","journal-title":"BIT"},{"key":"426_CR12_426","unstructured":"Knauer, C., Spillner, A.: Fixed\u2010parameter algorithms for finding crossing\u2010free spanning trees in geometric graphs. Tech. Rep. 06\u201307, Department of Computer Science, Friedrich\u2010Schiller\u2010Universit\u00e4t Jena (2006)"},{"key":"426_CR13_426","first-page":"49","volume-title":"Proceedings of the 32nd International Workshop on Graph\u2010Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 4271","author":"C. Knauer","year":"2006","unstructured":"Knauer, C., Spillner, A.: A\u00a0fixed\u2010parameter algorithm for the minimum weight triangulation problem based on small graph separators. In: Proceedings of the 32nd International Workshop on Graph\u2010Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol.\u00a04271, pp.\u00a049\u201357. Springer, New York (2006)"},{"volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","year":"1985","key":"426_CR14_426","unstructured":"Lawler, E., Lenstra, J., Rinnooy Kan, A., Shmoys, D.\u00a0(eds.): The Traveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"426_CR15_426","volume-title":"Proceedings 22nd Annual ACM Symposium on Computational Geometry, SoCG'06, Sedona, AZ, USA","author":"W. Mulzer","year":"2006","unstructured":"Mulzer, W., Rote, G.: Minimum Weight Triangulation is NP-hard. In: Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Association for Computing Machinery, New York 2006, pp.\u00a01\u201310"},{"key":"426_CR16_426","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed\u2010Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed\u2010Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"426_CR17_426","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.: The Euclidean travelling salesman problem is NP\u2011complete. Theor. Comput. Sci. 4, 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"426_CR18_426","first-page":"135","volume-title":"Proceedings of the 1st ACiD Workshop. Texts in Algorithmics, vol. 4","author":"A. Spillner","year":"2005","unstructured":"Spillner, A.: A\u00a0faster 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.\u00a04, pp.\u00a0135\u2013146. King's College, London (2005)"},{"key":"426_CR19_426","unstructured":"Spillner, A.: Optimal convex partitions of point sets with few inner points. In: Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG), 2005, pp.\u00a034\u201337"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T01:54:57Z","timestamp":1662170097000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_426"}},"subtitle":["2004; De\u012dneko, Hoffmann, Okamoto,\nWoeginger"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_426","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}