The convex recoloring problem: polyhedra, facets and computational experiments
From MaRDI portal
Publication:263202
DOI10.1007/s10107-015-0880-7zbMath1346.90609OpenAlexW2047226489MaRDI QIDQ263202
Phablo F. S. Moura, Alexandre S. Freire, Yoshiko Wakabayashi, Manoel B. 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
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items (7)
A GRASP for the convex recoloring problem in graphs ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability of generalized convex recoloring problems ⋮ Strong intractability results for generalized convex recoloring problems ⋮ 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
Cites Work
- The complexity of minimum convex coloring
- Quadratic kernelization for convex recoloring of trees
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
- 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
- On the Complexity of Solving or Approximating Convex Recoloring Problems
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- Algorithms and Data Structures
This page was built for publication: The convex recoloring problem: polyhedra, facets and computational experiments
