@inproceedings{681563c16cf14e978302bad4d3394a66,

title = "Column generation approach to the convex recoloring problem on a tree",

abstract = "The convex recoloring (CR) problem is to recolor the nodes of a colored graph at minimum number of color changes such that each color induces a connected subgraph. We adjust to the convex recoloring problem the column generation framework developed by Johnson et al. (Math Program 62:133–151, 1993). For the convex recoloring problem on a tree, the subproblem to generate columns can be solved in polynomial time by a dynamic programming algorithm. The column generation framework solves the convex recoloring problem on a tree with a large number of colors extremely fast.",

keywords = "Bioinformatics, Clustering problem, Column generation, Convex recoloring problem, Large scale optimization, Linear programming, Phylogenetic tree, Set partition problem",

author = "Sunil Chopra and Ergin Erdem and Eunseok Kim and Sangho Shim",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 16th International Conference on Modeling and Optimization: Theory and Applications, MOPTA 2016 ; Conference date: 17-08-2016 Through 19-08-2016",

year = "2017",

doi = "10.1007/978-3-319-66616-7_3",

language = "English (US)",

isbn = "9783319666150",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer New York LLC",

pages = "39--53",

editor = "Martin Takac and Tamas Terlaky",

booktitle = "Modeling and Optimization",

}