The convex recoloring problem: polyhedra, facets and computational experiments

DOI10.1007/S10107-015-0880-7zbMATH Open1346.90609OpenAlexW2047226489MaRDI QIDQ263202FDOQ263202

Authors Alexandre S. Freire, Phablo F. S. Moura, Yoshiko Wakabayashi, Manoel Campêlo, Karla Roberta Lima

Publication date 4 April 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-015-0880-7

zbMATH Keywords

phylogenetic treeinteger linear programmingbranch-and-cutconvex coloringfacetpolyhedral study

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• Convex Recoloring Revisited: Complexity and Exact Algorithms
• On the complexity of solving or approximating convex recoloring problems
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• A GRASP for the convex recoloring problem in graphs
• Efficient approximation of convex recolorings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Hardness and inapproximability of convex recoloring problems
• Total coloring and total matching: polyhedra and facets
• 1.5-approximation algorithm for the 2-convex recoloring problem
• 1.5-approximation algorithm for the 2-convex recoloring problem

Cites work

• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Algorithms and Data Structures
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Convex recoloring of paths
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Efficient approximation of convex recolorings
• On the complexity of solving or approximating convex recoloring problems
• Partial convex recolorings of trees and galled networks
• Quadratic kernelization for convex recoloring of trees
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• The complexity of minimum convex coloring

Cited in

(15)

• A heuristic for the convex recoloring problem in graphs
• Strong intractability results for generalized convex recoloring problems
• Strong intractability of generalized convex recoloring problems
• Column generation approach to the convex recoloring problem on a tree
• The minimum chromatic violation problem: a polyhedral study
• Facet-generating procedures for the maximum-impact coloring polytope
• Convex recoloring of paths
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A GRASP for the convex recoloring problem in graphs
• An extended formulation of the convex recoloring problem on a tree
• Efficient approximation of convex recolorings
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• An Exact Solution Method for the Political Districting Problem
• Total coloring and total matching: polyhedra and facets

This page was built for publication: The convex recoloring problem: polyhedra, facets and computational experiments

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