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

DOI10.1016/J.EJOR.2022.02.013MaRDI QIDQ2673556zbMATH OpenOpenAlexWikidataFDO

Authors Alexandre S. Freire, Phablo F. S. Moura, Joel C. Soares, Manoel 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

branch-and-priceconvex recoloringinteger programmingphylogenetic treepolyhedral study

Mathematics Subject Classification ID

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

Recommendations

• The convex recoloring problem: polyhedra, facets and computational experiments
• Convex recoloring of paths
• Convex recoloring of paths
• Column generation approach to the convex recoloring problem on a tree
• On the complexity of solving or approximating convex recoloring problems

Cites work

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

Cited in

(4)

• The -connected assignment problem
• An extended formulation of the convex recoloring problem on a tree
• Column generation approach to the convex recoloring problem on a tree
• A GRASP for the convex recoloring problem in graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673556)