Submodular Potential Function for the Minimum Color Spanning Tree Problem of Edge-colored Graphs
Jianhua Tu · Shinjang dashösi ilmiy jurnili · 2008
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.