{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T06:52:17Z","timestamp":1777013537023,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540792277","type":"print"},{"value":"9783540792284","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_43","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T01:07:56Z","timestamp":1209431276000},"page":"490-501","source":"Crossref","is-referenced-by-count":11,"title":["Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems"],"prefix":"10.1007","author":[{"given":"Oriana","family":"Ponta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Falk","family":"H\u00fcffner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","series-title":"Texts in Algorithmics","first-page":"19","volume-title":"Proc.\u00a03rd ACiD","author":"E.H. Bachoore","year":"2007","unstructured":"Bachoore, E.H., Bodlaender, H.L.: Convex recoloring of leaf-colored trees. In: Proc.\u00a03rd ACiD. Texts in Algorithmics, vol.\u00a09, pp. 19\u201333. College Publications, London (2007)"},{"key":"43_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. Theory of Computing Systems, (to appear, 2007)","DOI":"10.1007\/11671411_5"},{"key":"43_CR3","first-page":"67","volume-title":"Proc.\u00a039th STOC","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proc.\u00a039th STOC, pp. 67\u201374. ACM Press, New York (2007)"},{"issue":"1","key":"43_CR4","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2005.11.005","volume":"177","author":"C. Blum","year":"2007","unstructured":"Blum, C.: Revisiting dynamic programming for finding optimal subtrees in trees. European Journal of Operational Research\u00a0177(1), 102\u2013115 (2007)","journal-title":"European Journal of Operational Research"},{"key":"43_CR5","unstructured":"Bodlaender, H.L., Weyer, M.: Convex and connected recolorings of trees and graphs (unpublished manuscript, 2005)"},{"key":"43_CR6","series-title":"Texts in Algorithmics","first-page":"23","volume-title":"Proc.\u00a02nd ACiD","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Kernelization for convex recoloring. In: Proc.\u00a02nd ACiD. Texts in Algorithmics, vol.\u00a07, pp. 23\u201335. College Publications, London (2006)"},{"key":"43_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-73545-8_11","volume-title":"Computing and Combinatorics","author":"H.L. Bodlaender","year":"2007","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. In: Lin, G. (ed.) COCOON. LNCS, vol.\u00a04598, pp. 86\u201396. Springer, Heidelberg (2007)"},{"key":"43_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-540-73545-8_10","volume-title":"Computing and Combinatorics","author":"B. Chor","year":"2007","unstructured":"Chor, B., Fellows, M.R., Ragan, M.A., Razgon, I., Rosamond, F.A., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity. In: Lin, G. (ed.) COCOON. LNCS, vol.\u00a04598, pp. 75\u201385. Springer, Heidelberg (2007)"},{"key":"43_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)"},{"issue":"3","key":"43_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01(3), 195\u2013207 (1972)","journal-title":"Networks"},{"key":"43_CR11","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"43_CR12","first-page":"57","volume-title":"Proc.\u00a039th STOC","author":"M. F\u00fcrer","year":"2007","unstructured":"F\u00fcrer, M.: Faster integer multiplication. In: Proc.\u00a039th STOC, pp. 57\u201366. ACM Press, New York (2007)"},{"key":"43_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-540-72504-6_23","volume-title":"Theory and Applications of Models of Computation","author":"A. Lingas","year":"2007","unstructured":"Lingas, A., Wahlen, M.: On exact complexity of subgraph homeomorphism. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol.\u00a04484, pp. 256\u2013261. Springer, Heidelberg (2007)"},{"key":"43_CR14","unstructured":"Maffioli, F.: Finding a best subtree of a tree. Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, Italy (1991)"},{"key":"43_CR15","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) (to appear in Journal of Computer and System Sciences)"},{"issue":"7","key":"43_CR16","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. Journal of Computer and System Sciences\u00a073(7), 1078\u20131089 (2007)","journal-title":"Journal of Computer and System Sciences"},{"key":"43_CR17","unstructured":"Moran, S., Snir, S., Sung, W.-K.: Partial convex recolorings of trees and galled networks: Tight upper and lower bounds (February 2007) (manuscript)"},{"key":"43_CR18","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, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"43_CR19","volume-title":"The Fixed-Parameter Approach to the Convex Recoloring Problem","author":"O. Ponta","year":"2007","unstructured":"Ponta, O.: The Fixed-Parameter Approach to the Convex Recoloring Problem. Diplomarbeit, Mathematisches Institut, Ruprecht-Karls-Universit\u00e4t. Springer, Heidelberg (2007)"},{"issue":"2","key":"43_CR20","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 2O(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","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:14:24Z","timestamp":1619507664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_43","relation":{},"subject":[]}}