### 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.

Original language | English (US) |
---|---|

Title of host publication | Modeling and Optimization |

Subtitle of host publication | Theory and Applications- MOPTA, Selected Contributions |

Editors | Martin Takac, Tamas Terlaky |

Publisher | Springer New York LLC |

Pages | 39-53 |

Number of pages | 15 |

ISBN (Print) | 9783319666150 |

DOIs | |

State | Published - Jan 1 2017 |

Event | 16th International Conference on Modeling and Optimization: Theory and Applications, MOPTA 2016 - Bethlehem, United States Duration: Aug 17 2016 → Aug 19 2016 |

### Publication series

Name | Springer Proceedings in Mathematics and Statistics |
---|---|

Volume | 213 |

ISSN (Print) | 2194-1009 |

ISSN (Electronic) | 2194-1017 |

### Other

Other | 16th International Conference on Modeling and Optimization: Theory and Applications, MOPTA 2016 |
---|---|

Country | United States |

City | Bethlehem |

Period | 8/17/16 → 8/19/16 |

### Keywords

- Bioinformatics
- Clustering problem
- Column generation
- Convex recoloring problem
- Large scale optimization
- Linear programming
- Phylogenetic tree
- Set partition problem

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Column generation approach to the convex recoloring problem on a tree'. Together they form a unique fingerprint.

## Cite this

Chopra, S., Erdem, E., Kim, E., & Shim, S. (2017). Column generation approach to the convex recoloring problem on a tree. In M. Takac, & T. Terlaky (Eds.),

*Modeling and Optimization: Theory and Applications- MOPTA, Selected Contributions*(pp. 39-53). (Springer Proceedings in Mathematics and Statistics; Vol. 213). Springer New York LLC. https://doi.org/10.1007/978-3-319-66616-7_3