{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:36:04Z","timestamp":1756463764229},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642028816"},{"type":"electronic","value":"9783642028823"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02882-3_39","type":"book-chapter","created":{"date-parts":[[2009,7,10]],"date-time":"2009-07-10T06:49:21Z","timestamp":1247208561000},"page":"388-397","source":"Crossref","is-referenced-by-count":8,"title":["Convex Recoloring Revisited: Complexity and Exact Algorithms"],"prefix":"10.1007","author":[{"given":"Iyad A.","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","first-page":"41","volume":"144","author":"G. Agnarsson","year":"2000","unstructured":"Agnarsson, G., Greenlaw, R., Halld\u00f3rsson, M.: On powers of chordal graphs and their colorings. Congressus Numerantium\u00a0144, 41\u201365 (2000)","journal-title":"Congressus Numerantium"},{"issue":"1","key":"39_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 of Computing Systems\u00a043(1), 3\u201318 (2008)","journal-title":"Theory of Computing Systems"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Langston, M., Ragan, M., Rosamond, F., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 86\u201396. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-73545-8_11"},{"key":"39_CR4","unstructured":"Bodlaender, H., Weyer, M.: Convex and connected recoloring of trees and graphs (unpublished manuscript, 2005)"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Chor, B., Fellows, M., Ragan, M., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 75\u201385. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-73545-8_10"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O(20.288) independent set algorithm. In: Proceedings of SODA, pp. 18\u201325 (2006)","DOI":"10.1145\/1109557.1109560"},{"key":"39_CR7","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the Fifth British Combinatorial Conference, pp. 211\u2013226 (1975)"},{"issue":"5-6","key":"39_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F. Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters\u00a073(5-6), 181\u2013188 (2000)","journal-title":"Information Processing Letters"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a057. North-Holland Publishing Co., Amsterdam (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"39_CR10","first-page":"579","volume":"29","author":"R. Laskar","year":"1980","unstructured":"Laskar, R., Shier, D.: On chordal graphs. Congressus Numerantium\u00a029, 579\u2013588 (1980)","journal-title":"Congressus Numerantium"},{"issue":"5","key":"39_CR11","first-page":"850","volume":"74","author":"S. Moran","year":"2008","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. JCSS\u00a074(5), 850\u2013869 (2008)","journal-title":"JCSS"},{"key":"39_CR12","doi-asserted-by":"crossref","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.\u00a04978, pp. 490\u2013501. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-79228-4_43"},{"issue":"2","key":"39_CR13","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 2 O(k)poly(n) algorithm for the parameterized convex recoloring problem. Information Processing Letters\u00a0104(2), 53\u201358 (2007)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02882-3_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:44:49Z","timestamp":1558421089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02882-3_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642028816","9783642028823"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02882-3_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}