{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T07:28:39Z","timestamp":1775978919819,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540921813","type":"print"},{"value":"9783540921820","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-92182-0_5","type":"book-chapter","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T02:38:06Z","timestamp":1228876686000},"page":"16-27","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Minimum Convex Coloring"],"prefix":"10.1007","author":[{"given":"Frank","family":"Kammer","sequence":"first","affiliation":[]},{"given":"Torsten","family":"Tholey","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms\u00a02, 153\u2013177 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 276\u2013283 (2005)","DOI":"10.1145\/1060590.1060632"},{"key":"5_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":"5_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded tree width. Theoret. Comput. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms\u00a021, 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"5_CR6","doi-asserted-by":"publisher","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.\u00a011, 219\u2013229 (2006)","journal-title":"J. Comb. Optim."},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R.M. Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"J.F. Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. (ACM) SIGDA Newsletter\u00a05, 31\u201336 (1975)","journal-title":"(ACM) SIGDA Newsletter"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"5_CR11","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 recoloring. J. Comput. System Sci.\u00a073, 1078\u20131089 (2007)","journal-title":"J. Comput. System Sci."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B\u00a035, 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"5_CR13","unstructured":"Snir, S.: Computational Issues in Phylogenetic Reconstruction: Analytic Maximum Likelihood Solutions, and Convex Recoloring. Ph.D. Thesis, Department of Computer Science, Technion, Haifa, Israel (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92182-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T03:44:12Z","timestamp":1557978252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92182-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540921813","9783540921820"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92182-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}