{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:03Z","timestamp":1759638363558},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00453-010-9404-2","type":"journal-article","created":{"date-parts":[[2010,3,26]],"date-time":"2010-03-26T10:16:02Z","timestamp":1269598562000},"page":"362-388","source":"Crossref","is-referenced-by-count":9,"title":["Quadratic Kernelization for Convex Recoloring of Trees"],"prefix":"10.1007","volume":"61","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[]},{"given":"Mark A.","family":"Ragan","sequence":"additional","affiliation":[]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Weyer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,3,27]]},"reference":[{"key":"9404_CR1","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Proc. 6th ACM-SIAM ALENEX, pp. 62\u201369. ACM-SIAM (2004)"},{"key":"9404_CR2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/s10479-006-0045-4","volume":"146","author":"J. Alber","year":"2006","unstructured":"Alber, J., Betzler, N., Niedermeier, R.: Experiments in data reduction for optimal domination in networks. Ann. Oper. Res. 146, 105\u2013117 (2006)","journal-title":"Ann. Oper. Res."},{"key":"9404_CR3","first-page":"363","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating sets. J.\u00a0ACM 51, 363\u2013384 (2004)","journal-title":"J.\u00a0ACM"},{"key":"9404_CR4","doi-asserted-by":"crossref","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, 3\u201318 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9404_CR5","first-page":"160","volume":"78","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 78, 160\u2013174 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9404_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/978-3-540-73545-8_11","volume-title":"Proceedings 13th Annual International Computing and Combinatorics Conference, COCOON 2007, Heidelberg","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M., Ragan, M., Rosamond, F., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Lin, G. (ed.) Proceedings 13th Annual International Computing and Combinatorics Conference, COCOON 2007, Heidelberg. Lecture Notes in Computer Science, vol. 4598, pp. 86\u201396. Springer, Berlin (2007)"},{"key":"9404_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Proceedings 2nd International Workshop on Parameterized and Exact Computation, IWPEC 2006","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.) Proceedings 2nd International Workshop on Parameterized and Exact Computation, IWPEC 2006. Lecture Notes in Computer Science, vol. 4169, pp. 192\u2013202. Springer, Berlin (2006)"},{"key":"9404_CR8","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37, 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"key":"9404_CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10878-006-7135-8","volume":"11","author":"X. Chen","year":"2006","unstructured":"Chen, X., Hu, X., Shuai, T.: Inapproximability and approximability of maximal tree routing and coloring. J. Comb. Optim. 11, 219\u2013229 (2006)","journal-title":"J. Comb. Optim."},{"key":"9404_CR10","doi-asserted-by":"crossref","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. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"9404_CR11","series-title":"Contemp. Math.","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1090\/conm\/147\/01200","volume-title":"Graph Structure Theory, Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Seattle WA, June 1991","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B.: Graph grammars, monadic second-order logic and the theory of graph minors. In: Robertson, N., Seymour, P. (eds.) Graph Structure Theory, Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Seattle WA, June 1991. Contemp. Math., vol. 147, pp. 565\u2013590. Am. Math. Soc., Providence (1993)"},{"key":"9404_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming, Proceedings of the 36th International Colloquium, ICALP 2009, Part\u00a0I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Automata, Languages and Programming, Proceedings of the 36th International Colloquium, ICALP 2009, Part\u00a0I. Lecture Notes in Computer Science, vol. 5555, pp. 378\u2013389. Springer, Berlin (2009)"},{"key":"9404_CR13","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, Berlin (1999)"},{"key":"9404_CR14","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9404_CR15","first-page":"133","volume-title":"Proceedings of the 38th Annual Symposium on Theory of Computing, STOC 2006","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 38th Annual Symposium on Theory of Computing, STOC 2006, pp. 133\u2013142. ACM, New York (2008)"},{"key":"9404_CR16","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1093\/comjnl\/bxm049","volume":"51","author":"J. Gramm","year":"2008","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Comput. J. 51, 79\u2013101 (2008)","journal-title":"Comput. J."},{"key":"9404_CR17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38, 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"9404_CR18","unstructured":"H\u00fcffner, F.: Algorithms and experiments for parameterized approaches to hard graph problems. PhD thesis, Friedrich-Schiller University, Jena, Germany (2007)"},{"key":"9404_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-540-92182-0_5","volume-title":"Proceedings 19th International Symposium on Algorithms and Computation, ISAAC 2008","author":"F. Kammer","year":"2008","unstructured":"Kammer, F., Tholey, T.: The complexity of minimum convex coloring. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) Proceedings 19th International Symposium on Algorithms and Computation, ISAAC 2008. Lecture Notes in Computer Science, vol. 5369, pp. 16\u201327. Springer, Berlin (2008)"},{"key":"9404_CR20","doi-asserted-by":"crossref","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, 1078\u20131089 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"9404_CR21","doi-asserted-by":"crossref","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, 850\u2013869 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9404_CR22","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packing: Structural properties and algorithms. Math. Program. 8, 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"9404_CR23","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, London (2006)"},{"key":"9404_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/978-3-540-79228-4_43","volume-title":"Proceedings 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008","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.) Proceedings 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008. Lecture Notes in Computer Science, vol. 4978, pp. 490\u2013501. Springer, Berlin (2008)"},{"key":"9404_CR25","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 115\u2013119 (2009)","DOI":"10.1137\/1.9781611973068.13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-010-9404-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T13:15:06Z","timestamp":1558962906000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9404-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,27]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9404"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9404-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,27]]}}}