次模函数近似算法求最小颜色生成树(英文)  

Submodular Potential Function for the Minimum Color Spanning Tree Problem of Edge-colored Graphs

作　　者：李学良[1] 涂建华[1] 

机构地区：[1]南开大学组合数学中心,天津300071

出　　处：《新疆大学学报（自然科学版）》2008年第4期391-394,共4页Journal of Xinjiang University(Natural Science Edition)

基　　金：Supported by NSFC;Supported by PCSIRT;Supported by the "973" programm

摘　　要：给定图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.

关 键 词：边着色图 最小颜色生成树(MCST) 最大颜色匹配(MCM) 次模函数 近似算法 

分 类 号：O157.5[理学—数学]