{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:19Z","timestamp":1759638499564},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_11","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"86-96","source":"Crossref","is-referenced-by-count":8,"title":["Quadratic Kernelization for Convex Recoloring of Trees"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark A.","family":"Ragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Weyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating sets. J. ACM\u00a051, 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/11671411_5","volume-title":"Approximation and Online Algorithms","author":"R. Bar-Yehuda","year":"2006","unstructured":"Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 55\u201368. Springer, Heidelberg (2006)"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K. Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S., Rosamond, F.A.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 192\u2013202. Springer, Heidelberg (2006)"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Chor, B., Fellows, M., Ragan, M., Rosamond, F., Razgon, I., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. In: Proceedings COCOON (2007)","DOI":"10.1007\/978-3-540-73545-8_10"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"11_CR9","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":"11_CR10","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"11_CR11","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. To appear in The Computer Journal."},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/11534273_20","volume-title":"Algorithms and Data Structures","author":"S. Moran","year":"2005","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results, and algorithms. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 218\u2013232. Springer, Heidelberg (2005)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/11538462_17","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"S. Moran","year":"2005","unstructured":"Moran, S., Snir, S.: Efficient approximation of convex recolorings. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 192\u2013208. Springer, Heidelberg (2005)"},{"key":"11_CR14","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:17:43Z","timestamp":1619518663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}