{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T07:28:41Z","timestamp":1775978921314,"version":"3.50.1"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319295152","type":"print"},{"value":"9783319295169","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-29516-9_25","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T05:05:19Z","timestamp":1455858319000},"page":"299-311","source":"Crossref","is-referenced-by-count":3,"title":["1.5-Approximation Algorithm for the 2-Convex Recoloring Problem"],"prefix":"10.1007","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilad","family":"Kutiel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,20]]},"reference":[{"key":"25_CR1","unstructured":"Bachoore, E.H., Bodlaender, H.L.: Convex recoloring of leaf-colored trees. Technical report UU-CS\u2013010, Department of Information and Computing Sciences, Utrecht University (2006)"},{"issue":"1","key":"25_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00224-007-9069-7","volume":"43","author":"R Bar-Yehuda","year":"2008","unstructured":"Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. Theory Comput. Syst. 43(1), 3\u201318 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"25_CR3","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s00453-010-9404-2","volume":"61","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Quadratic kernelization for convex recoloring of trees. Algorithmica 61(2), 362\u2013388 (2011)","journal-title":"Algorithmica"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1007\/978-3-642-38768-5_54","volume-title":"Computing and Combinatorics","author":"MB Camp\u00ealo","year":"2013","unstructured":"Camp\u00ealo, M.B., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y.: On the complexity of solving or approximating convex recoloring problems. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 614\u2013625. Springer, Heidelberg (2013)"},{"issue":"6","key":"25_CR5","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1016\/j.dam.2011.09.022","volume":"160","author":"F Kammer","year":"2012","unstructured":"Kammer, F., Tholey, T.: The complexity of minimum convex coloring. Discrete Appl. Math. 160(6), 810\u2013833 (2012)","journal-title":"Discrete Appl. Math."},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-642-02882-3_39","volume-title":"Computing and Combinatorics","author":"IA Kanj","year":"2009","unstructured":"Kanj, I.A., Kratsch, D.: Convex recoloring revisited: complexity and exact algorithms. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol. 5609, pp. 388\u2013397. Springer, Heidelberg (2009)"},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5, 45\u201368 (1975)","journal-title":"Networks"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1016\/j.dam.2013.02.034","volume":"164","author":"KR Lima","year":"2014","unstructured":"Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Discrete Appl. Math. 164, 450\u2013459 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"25_CR9","doi-asserted-by":"publisher","first-page":"1078","DOI":"10.1016\/j.jcss.2007.03.006","volume":"73","author":"S Moran","year":"2007","unstructured":"Moran, S., Snir, S.: Efficient approximation of convex recolorings. J. Comput. Syst. Sci. 73(7), 1078\u20131089 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"25_CR10","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1016\/j.jcss.2007.10.003","volume":"74","author":"S Moran","year":"2008","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. J. Comput. Syst. Sci. 74(5), 850\u2013869 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-540-79228-4_43","volume-title":"Theory and Applications of Models of Computation","author":"O Ponta","year":"2008","unstructured":"Ponta, O., H\u00fcffner, F., Niedermeier, R.: Speeding up dynamic programming for some NP-hard graph recoloring problems. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 490\u2013501. Springer, Heidelberg (2008)"},{"issue":"2","key":"25_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2007.05.007","volume":"104","author":"I Razgon","year":"2007","unstructured":"Razgon, I.: A \n                    \n                      \n                    \n                    $${2^{O(k)}}\\text{ poly }(n)$$\n                   algorithm for the parameterized convex recoloring problem. Inf. Process. Lett. 104(2), 53\u201358 (2007)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29516-9_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T14:53:43Z","timestamp":1559400823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29516-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319295152","9783319295169"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29516-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}