کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419023 | 681732 | 2014 | 10 صفحه PDF | دانلود رایگان |
Let (T,C)(T,C) be a pair consisting of a tree TT and a coloring CC of its vertices. We say that CC is a convex coloring if, for each color cc, the vertices in TT with color cc induce a subtree of TT. The convex recoloring problem (of trees) is defined as follows. Given a pair (T,C)(T,C), find a recoloring of a minimum number of vertices of TT such that the resulting coloring is convex. This problem, known to be NP-hard, was motivated by problems on phylogenetic trees.We investigate here the convex recoloring problem on paths, denoted here as CRP. The main result concerns an approximation algorithm for a special case of CRP, denoted here as 22-CRP, restricted to paths in which the number of vertices of each color is at most 22, a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir in 2007, who showed a 22-approximation algorithm. We show in this paper a 3/23/2-approximation algorithm for 22-CRP and show that its ratio analysis is tight.We also present an integer programming formulation for CRP and discuss some computational results obtained by exploring this formulation.
Journal: Discrete Applied Mathematics - Volume 164, Part 2, 19 February 2014, Pages 450–459