@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",
}