{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T21:27:52Z","timestamp":1780608472696,"version":"3.54.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T00:00:00Z","timestamp":1480464000000},"content-version":"unspecified","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":[[2017,10]]},"DOI":"10.1007\/s10107-016-1094-3","type":"journal-article","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T14:33:41Z","timestamp":1480516421000},"page":"529-548","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["An extended formulation of the convex recoloring problem on a tree"],"prefix":"10.1007","volume":"165","author":[{"given":"Sunil","family":"Chopra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bartosz","family":"Filipecki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kangbok","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minseok","family":"Ryu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sangho","family":"Shim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathieu","family":"Van Vyve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,11,30]]},"reference":[{"key":"1094_CR1","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":"1094_CR2","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1007\/978-3-642-38768-5_54","volume":"7936","author":"M Camp\u00ealo","year":"2013","unstructured":"Camp\u00ealo, M., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y.: On the complexity of solving or approximating convex recoloring problems. Lect. Notes Comput. Sci. 7936, 614\u2013625 (2013)","journal-title":"Lect. Notes Comput. Sci."},{"key":"1094_CR3","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/j.endm.2013.10.036","volume":"44","author":"M Camp\u00ealo","year":"2013","unstructured":"Camp\u00ealo, M., Lima, K.R., Moura, P., Wakabayashi, Y.: Polyhedral studies on the CR problem. Electron. Notes Discret. Math. 44, 233\u2013238 (2013)","journal-title":"Electron. Notes Discret. Math."},{"key":"1094_CR4","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10107-015-0880-7","volume":"156","author":"M Camp\u00ealo","year":"2016","unstructured":"Camp\u00ealo, M., Freire, A.S., Lima, K.R., Moura, P., Wakabayashi, Y.: The convex recoloring problem: polyhedra, facets and computational experiments. Math. Progr. 156, 303\u2013330 (2016)","journal-title":"Math. Progr."},{"key":"1094_CR5","first-page":"7","volume":"73","author":"S Chopra","year":"1996","unstructured":"Chopra, S., Owen, J.L.: Extended formulations for the A-cut problem. Math. Progr. 73, 7\u201330 (1996)","journal-title":"Math. Progr."},{"key":"1094_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.R.: The partition problem. Math. Progr. 59, 87\u2013115 (1993)","journal-title":"The partition problem. Math. Progr."},{"key":"1094_CR7","first-page":"75","volume":"4598","author":"B Chor","year":"2007","unstructured":"Chor, B., Fellows, M., Ragan, M., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. Lect. Comput. Sci. 4598, 75\u201385 (2007)","journal-title":"Lect. Comput. Sci."},{"key":"1094_CR8","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/j.orl.2015.06.011","volume":"43","author":"M Conforti","year":"2015","unstructured":"Conforti, M., Kaibel, V., Walter, M., Weltge, S.: Subgraph polytopes and independence polytopes of count matroids. Oper. Res. Lett. 43, 457\u2013460 (2015)","journal-title":"Oper. Res. Lett."},{"key":"1094_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8, 1\u201348 (2010)","journal-title":"4OR"},{"key":"1094_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X.: The Steiner tree polytope and related polyhedra. Math. Progr. 63, 157\u2013182 (1994)","journal-title":"Math. Progr."},{"key":"1094_CR11","unstructured":"Kaibel, V.: Extended Formulations in Combinatorial Optimization, arXiv:1104.1023v1 [math.CO] 6 Apr (2011), manuscript"},{"key":"1094_CR12","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. Discret. Appl. Math. 160, 810\u2013833 (2012)","journal-title":"Discret. Appl. Math."},{"key":"1094_CR13","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/978-3-642-02882-3_39","volume":"5609","author":"IA Kanj","year":"2009","unstructured":"Kanj, I.A., Kratsch, D.: Convex recoloring revisited: complexity and exact algorithms. Lect. Notes Comput. Sci. 5609, 388\u2013397 (2009)","journal-title":"Lect. Notes Comput. Sci."},{"key":"1094_CR14","volume-title":"Greedoids, Algorithms and Combinatorics","author":"B Korte","year":"1991","unstructured":"Korte, B., Lov\u00e1sz, L., Schrader, R.: Greedoids, Algorithms and Combinatorics, vol. 4. Springer, Berlin (1991)"},{"key":"1094_CR15","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1016\/j.dam.2013.02.034","volume":"164","author":"KR Lima","year":"2014","unstructured":"Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Discret. Appl. Math. 164, 450\u2013459 (2014)","journal-title":"Discret. Appl. Math."},{"key":"1094_CR16","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"},{"key":"1094_CR17","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":"1094_CR18","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":"1094_CR19","doi-asserted-by":"crossref","first-page":"42","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, 42 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"1094_CR20","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)"},{"key":"1094_CR21","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, TAMC08, pp. 490\u2013501. Springer (2008)","DOI":"10.1007\/978-3-540-79228-4_43"},{"key":"1094_CR22","doi-asserted-by":"crossref","unstructured":"Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: Michael J\u00fcnger, T., Liebling, D.N., George, N., William, P., Gerhard, R., Giovanni, R., Laurence, W. (eds.) Fifty Years of Integer Programming 1958\u20132008, pp. 431\u2013502. Springer, Berlin (2010)","DOI":"10.1007\/978-3-540-68279-0_13"},{"key":"1094_CR23","unstructured":"Wang, Y., Buchanan, A., Butenko, S.: On Imposing Connectivity Constraints in Integer Programs. www.optimization-online.org\/DB_HTML\/2015\/02\/4768.html"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1094-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1094-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1094-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T22:10:23Z","timestamp":1718921423000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1094-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,30]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["1094"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1094-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,30]]}}}