The convex recoloring problem: polyhedra, facets and computational experiments
DOI10.1007/S10107-015-0880-7zbMATH Open1346.90609OpenAlexW2047226489MaRDI QIDQ263202FDOQ263202
Phablo F. S. Moura, Alexandre S. Freire, Manoel Campêlo, Karla Roberta Lima, Yoshiko Wakabayashi
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
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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10)
Cites Work
- A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
- Efficient approximation of convex recolorings
- Convex recoloring of paths
- Partial convex recolorings of trees and galled networks
- Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
- Connected Coloring Completion for General Graphs: Algorithms and Complexity
- The complexity of minimum convex coloring
- On the Complexity of Solving or Approximating Convex Recoloring Problems
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- Algorithms and Data Structures
- Quadratic kernelization for convex recoloring of trees
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
Cited In (12)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Facet-generating procedures for the maximum-impact coloring polytope
- A GRASP for the convex recoloring problem in graphs
- A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
- Efficient approximation of convex recolorings
- Total coloring and total matching: polyhedra and facets
- An extended formulation of the convex recoloring problem on a tree
- Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
- A heuristic for the convex recoloring problem in graphs
- An Exact Solution Method for the Political Districting Problem
- Strong intractability results for generalized convex recoloring problems
- Strong intractability of generalized convex recoloring problems
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)
