Efficient approximation of convex recolorings
Efficient approximation of convex recolorings
复制标题
DOI：
10.1016/j.jcss.2007.03.006
复制
发表时间：
2007-11-01
影响因子：
1.1
通讯作者：
Snir, Sagi
中科院分区：
文献类型：
--
作者：
Moran, Shlomo;Snir, Sagi
如果一棵树的任何颜色的顶点都有连通的子树，那么它的着色就是凸的；如果局部着色（为某些顶点分配颜色）可以完成凸（全部）着色，则该着色是凸的。树的凸着色出现在诸如系统发育、语言学等领域，例如，一个完美的系统发育树是其中每个字符的状态诱导树的凸着色。对完美系统发育的研究通常集中在寻找一棵树，使其顶点的预定部分颜色很少是凸的。当树的着色不是凸的，我们希望知道它离凸的“有多远”。在[S。Moran， S. Snir，字符串和树的凸重着色：定义，硬度结果和算法，in: WADS, 2005, pp. 218-232；j .第一版。系统科学。[提交出版]，定义了这个距离的自然度量，称为重新着色距离：使着色凸所需的顶点颜色变化的最小数量。这可以看作是最小化“异常顶点”的数量。最接近的凸着色。这个问题被证明是np困难的，即使对有色弦也是如此。在本文中，我们继续了[S。Moran， S. Snir，字符串和树的凸重着色：定义，硬度结果和算法，in: WADS, 2005, pp. 218-232；j .第一版。系统科学。[提交发表]，并提出了一个运行时间为O（cn）的字符串凸重着色的2-近似算法，其中c是颜色的数量，n是输入的大小，以及一个0 (cn 2) 3-近似算法用于树的凸重着色。(c) 2007爱思唯尔公司版权所有。
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 arises in areas such as phylogenetics, linguistics, etc., e.g., 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 [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218-232; J. Comput. System Sci., submitted for publication], 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.rt. a closest convex coloring. The problem was proved to be NP-hard even for colored strings. In this paper we continue the work of [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218-232; J. Comput. System Sci., submitted for publication], 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 0 (cn 2) 3-approximation algorithm for convex recoloring of trees. (c) 2007 Elsevier Inc. All rights reserved.