{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:38:57Z","timestamp":1725471537337},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540483816"},{"type":"electronic","value":"9783540483823"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11917496_5","type":"book-chapter","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T06:16:13Z","timestamp":1161152173000},"page":"49-57","source":"Crossref","is-referenced-by-count":4,"title":["A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators"],"prefix":"10.1007","author":[{"given":"Christian","family":"Knauer","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Spillner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","first-page":"9","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. Annals of Discrete Mathematics\u00a012, 9\u201312 (1982)","journal-title":"Annals of Discrete Mathematics"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/S0022-0000(03)00072-2","volume":"67","author":"J. Alber","year":"2003","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Graph separators: a parameterized view. Journal of Computer and System Sciences\u00a067, 808\u2013832 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.orl.2005.01.002","volume":"34","author":"V.G. Deineko","year":"2006","unstructured":"Deineko, V.G., Hoffmann, M., Okamoto, Y., Woeginger, G.J.: The traveling salesman problem with few inner points. Operations Research Letters\u00a034(1), 106\u2013110 (2006)","journal-title":"Operations Research Letters"},{"key":"5_CR4","first-page":"238","volume-title":"Proc. Symposium on Computational Geometry","author":"M.T. Dickerson","year":"1995","unstructured":"Dickerson, M.T., McElfresh, S.A., Montague, M.H.: New algorithms and empirical findings on minimum weight triangulation heuristics. In: Proc. Symposium on Computational Geometry, pp. 238\u2013247. ACM Press, New York (1995)"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H.N. Djidjev","year":"1997","unstructured":"Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Informatica\u00a034, 231\u2013243 (1997)","journal-title":"Acta Informatica"},{"key":"5_CR6","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, Heidelberg (1999)"},{"key":"5_CR7","unstructured":"Grantson, M.: Fixed-parameter algorithms and other results for optimal partitions. Licentiate Thesis, Lund University, Sweden (2004)"},{"key":"5_CR8","unstructured":"Grantson, M., Borgelt, C., Levcopoulos, C.: A fixed parameter algorithm for minimum weight triangulation: Analysis and experiments. Technical Report LU-CS-TR:2005-234, Lund University, Sweden (2005)"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1007\/11602613_98","volume-title":"Algorithms and Computation","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. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 984\u2013994. Springer, Heidelberg (2005)"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/11589440_9","volume-title":"Discrete and Computational Geometry","author":"M. Grantson","year":"2005","unstructured":"Grantson, M., Levcopoulos, C.: A fixed-parameter algorithm for the minimum number convex partition problem. In: Akiyama, J., Kano, M., Tan, X. (eds.) JCDCG 2004. LNCS, vol.\u00a03742, pp. 83\u201394. Springer, Heidelberg (2005)"},{"issue":"3","key":"5_CR11","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. Computational Geometry\u00a034(3), 149\u2013158 (2006)","journal-title":"Computational Geometry"},{"key":"5_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":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-63890-3_41","volume-title":"Algorithms and Computation","author":"Y. Kyoda","year":"1997","unstructured":"Kyoda, Y., Imai, K., Takeuchi, F., Tajima, A.: A branch-and-cut approach for minimum weight triangulation. In: Leong, H.-V., Jain, S., Imai, H. (eds.) ISAAC 1997. LNCS, vol.\u00a01350, pp. 384\u2013393. Springer, Heidelberg (1997)"},{"key":"5_CR14","first-page":"392","volume-title":"Proc. Symposium on Discrete Algorithms","author":"C. Levcopoulos","year":"1996","unstructured":"Levcopoulos, C., Krznaric, D.: Quasi-greedy triangulations approximating the minimum weight triangulation. In: Proc. Symposium on Discrete Algorithms, pp. 392\u2013401. ACM Press, New York (1996)"},{"key":"5_CR15","unstructured":"Lingas, A.: Subexponential-time algorithms for minimum weight triangulation and related problems. In: Proc. Canadian Conference on Computational Geometry (1998)"},{"key":"5_CR16","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 Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09, 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences\u00a032, 265\u2013279 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR19","first-page":"1","volume-title":"Proc. Symposium on Computational Geometry","author":"W. Mulzer","year":"2006","unstructured":"Mulzer, W., Rote, G.: Minimum weight triangulation is NP-hard. In: Proc. Symposium on Computational Geometry, pp. 1\u201310. ACM Press, New York (2006)"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/0196-6774(87)90020-4","volume":"8","author":"D.A. Plaisted","year":"1987","unstructured":"Plaisted, D.A., Hong, J.: A heuristic triangulation algorithm. Journal of Algorithms\u00a08, 405\u2013437 (1987)","journal-title":"Journal of Algorithms"},{"key":"5_CR21","first-page":"316","volume-title":"Proc. Symposium on Theory of Computing","author":"J. Remy","year":"2006","unstructured":"Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: Proc. Symposium on Theory of Computing, pp. 316\u2013325. ACM Press, New York (2006)"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1145\/1109557.1109652","volume-title":"Proc. Symposium on Discrete Algorithms","author":"M. Sharir","year":"2006","unstructured":"Sharir, M., Welzl, E.: On the number of crossing-free matchings (cycles, and partitions). In: Proc. Symposium on Discrete Algorithms, pp. 860\u2013869. ACM Press, New York (2006)"},{"key":"5_CR23","unstructured":"Spillner, A.: A faster algorithm for the minimum weight triangulation problem with few inner points. In: Proc. Algorithms and Complexity in Durham Workshop, pp. 135\u2013146. KCL Publications (2005)"},{"key":"5_CR24","unstructured":"Spillner, A.: Optimal convex partitions of point sets with few inner points. In: Proc. Canadian Conference on Computational Geometry, pp. 34\u201337 (2005)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11917496_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:42:34Z","timestamp":1619509354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11917496_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540483816","9783540483823"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11917496_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}