Computer Science – Data Structures and Algorithms
Scientific paper
2005-05-27
Computer Science
Data Structures and Algorithms
Scientific paper
A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arise in areas such as phylogenetics, linguistics, etc. eg, a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex. When a coloring of a tree is not convex, it is desirable to know "how far" it is from a convex one. In [19], a natural measure for this distance, called the recoloring distance was defined: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of "exceptional vertices" w.r.t. to a closest convex coloring. The problem was proved to be NP-hard even for colored string. In this paper we continue the work of [19], and present a 2-approximation algorithm of convex recoloring of strings whose running time O(cn), where c is the number of colors and n is the size of the input, and an O(cn^2)-time 3-approximation algorithm for convex recoloring of trees.
Moran Shlomo
Snir Sagi
No associations
LandOfFree
Efficient Approximation of Convex Recolorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Approximation of Convex Recolorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Approximation of Convex Recolorings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-80312