Strong inequalities and a branch-and-price algorithm for the convex recoloring problem

DOI10.1016/j.ejor.2022.02.013OpenAlexW4211176253WikidataQ113875424 ScholiaQ113875424MaRDI QIDQ2673556

Joel C. Soares, Alexandre S. Freire, Phablo F. S. Moura, Manoel B. Campêlo

Publication date: 10 June 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2022.02.013

zbMATH Keywords

integer programmingbranch-and-pricephylogenetic treepolyhedral studyconvex recoloring

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The convex recoloring problem: polyhedra, facets and computational experiments
• The complexity of minimum convex coloring
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Min-cut clustering
• 1.5-approximation algorithm for the 2-convex recoloring problem
• An extended formulation of the convex recoloring problem on a tree
• Column generation approach to the convex recoloring problem on a tree
• Strong intractability results for generalized convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• Efficient approximation of convex recolorings
• A random tree model associated with random graphs
• Convex Recoloring Revisited: Complexity and Exact Algorithms

This page was built for publication: Strong inequalities and a branch-and-price algorithm for the convex recoloring problem