{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T20:56:33Z","timestamp":1780606593781,"version":"3.54.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,3,4]],"date-time":"2015-03-04T00:00:00Z","timestamp":1425427200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s10107-015-0880-7","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T01:17:37Z","timestamp":1425345457000},"page":"303-330","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The convex recoloring problem: polyhedra, facets and computational experiments"],"prefix":"10.1007","volume":"156","author":[{"given":"Manoel","family":"Camp\u00ealo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandre S.","family":"Freire","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karla R.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phablo F. S.","family":"Moura","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,3,4]]},"reference":[{"issue":"2","key":"880_CR1","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/s00453-010-9404-2","volume":"61","author":"HL Bodlaender","year":"2011","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. Algorithmica 61(2), 362\u2013388 (2011)","journal-title":"Algorithmica"},{"key":"880_CR2","doi-asserted-by":"crossref","unstructured":"Camp\u00ealo, M., Lima, K.R., Moura, P.F., Wakabayashi, Y.: Polyhedral studies on the convex recoloring problem. Electron. Notes Discrete Math. 44(0), 233\u2013238 (2013); [In: Proceedings of LAGOS\u201913 - VII Latin-American Algorithms, Graphs and Optimization Symposium]","DOI":"10.1016\/j.endm.2013.10.036"},{"key":"880_CR3","doi-asserted-by":"crossref","unstructured":"Camp\u00ealo, M.B., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y.: On the complexity of solving or approximating convex recoloring problems. Lecture Notes in Computer Science 7936, 614\u2013625 (2013); [In: Proceedings of the 19th International Conference on Computing and Combinatorics]","DOI":"10.1007\/978-3-642-38768-5_54"},{"key":"880_CR4","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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4598, 75\u201385 (2007)","DOI":"10.1007\/978-3-540-73545-8_10"},{"key":"880_CR5","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.dam.2011.09.022","volume":"160","author":"F Kammer","year":"2012","unstructured":"Kammer, F., Tholey, T.: The complexity of minimum convex coloring. Discrete Appl. Math. 160, 810\u2013833 (2012)","journal-title":"Discrete Appl. Math."},{"key":"880_CR6","doi-asserted-by":"crossref","unstructured":"Kanj, I.A., Kratsch, D.: Convex recoloring revisited: Complexity and exact algorithms. In: Proceedings of the 15th Annual International Conference on Computing and Combinatorics, COCOON \u201909, pp. 388\u2013397 (2009)","DOI":"10.1007\/978-3-642-02882-3_39"},{"key":"880_CR7","doi-asserted-by":"crossref","unstructured":"Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Electron. Notes Discrete Math. 37(0), 165\u2013170 (2011); In: LAGOS\u201911 - VI Latin-American Algorithms, Graphs and Optimization Symposium","DOI":"10.1016\/j.endm.2011.05.029"},{"key":"880_CR8","doi-asserted-by":"crossref","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results, and algorithms. In: Proceedings WADS 2005: 9th International Workshop on Algorithms and Data Structures, pp. 218\u2013232 (2005)","DOI":"10.1007\/11534273_20"},{"issue":"7","key":"880_CR9","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(7), 1078\u20131089 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"880_CR10","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(5), 850\u2013869 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"880_CR11","doi-asserted-by":"crossref","first-page":"42:1","DOI":"10.1145\/2000807.2000810","volume":"7","author":"S Moran","year":"2011","unstructured":"Moran, S., Snir, S., Sung, W.K.: Partial convex recolorings of trees and galled networks: tight upper and lower bounds. ACM Trans. Algorithms 7(4), 42:1\u201342:20 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"880_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: Proceedings of the 5th international conference on Theory and applications of models of computation, TAMC\u201908, pp. 490\u2013501. Springer, (2008)","DOI":"10.1007\/978-3-540-79228-4_43"},{"issue":"2","key":"880_CR13","doi-asserted-by":"crossref","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)$$ 2 O ( k ) p o l y ( n ) algorithm for the parameterized convex recoloring problem. Inf. Process. Lett. 104(2), 53\u201358 (2007)","journal-title":"Inf. Process. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0880-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0880-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0880-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T10:19:53Z","timestamp":1566382793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0880-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,4]]},"references-count":13,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["880"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0880-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,4]]}}}