Convex recoloring of paths
From MaRDI portal
Publication:2448880
DOI10.1016/j.dam.2013.02.034zbMath1288.05095OpenAlexW2172993755MaRDI QIDQ2448880
Yoshiko Wakabayashi, Karla Roberta Lima
Publication date: 5 May 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.034
Trees (05C05) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)
Related Items
1.5-approximation algorithm for the 2-convex recoloring problem, An extended formulation of the convex recoloring problem on a tree, Strong intractability results for generalized convex recoloring problems, Hardness and inapproximability of convex recoloring problems, The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
Cites Work
- Efficient approximation of convex recolorings
- Convex Recoloring of Paths
- The Complexity of Minimum Convex Coloring
- Connected Coloring Completion for General Graphs: Algorithms and Complexity
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- Algorithms and Data Structures
- Approximation and Online Algorithms