Column generation approach to the convex recoloring problem on a tree

Sunil Chopra, Ergin Erdem, Eunseok Kim, Sangho Shim*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 languageEnglish (US)
Title of host publicationModeling and Optimization
Subtitle of host publicationTheory and Applications- MOPTA, Selected Contributions
EditorsMartin Takac, Tamas Terlaky
PublisherSpringer New York LLC
Pages39-53
Number of pages15
ISBN (Print)9783319666150
DOIs
StatePublished - Jan 1 2017
Event16th International Conference on Modeling and Optimization: Theory and Applications, MOPTA 2016 - Bethlehem, United States
Duration: Aug 17 2016Aug 19 2016

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume213
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Other

Other16th International Conference on Modeling and Optimization: Theory and Applications, MOPTA 2016
CountryUnited States
CityBethlehem
Period8/17/168/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