摘要
给定图G并对其进行边着色,G的最小颜色生成树(MCST)问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论(贪婪算法的思想)给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.
Given a graph G and each edge of G a color, the minimum color spanning tree problem of the edge colored graph G is to find a spanning tree of G whose edge set consists of the smallest possible number of colors. The problem was shown to be NP-and APX-complete, thus it cannot be approximated within a constant factor. In this paper, we use submodular potential function, an important general theory about greedy approximations, to produce an approximation solution to the minimum color spanning tree problem,and the performance ratio cannot be improved any further.
出处
《新疆大学学报（自然科学版）》
CAS
2008年第4期391-394,共4页
Journal of Xinjiang University(Natural Science Edition)
基金
Supported by NSFC
Supported by PCSIRT
Supported by the "973" programm
