李学良, 涂建华. 次模函数近似算法求最小颜色生成树(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 112(4): 391-394.DOI：
次模函数近似算法求最小颜色生成树(英文)
摘要
给定图G并对其进行边着色
G的最小颜色生成树(MCST)问题是指
找出G的一棵生成树
使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的
从而此问题没有近似比为常数的近似算法.本文中
我们利用次模函数理论(贪婪算法的思想)给出最小颜色生成树问题的一个近似算法
且此算法的近似比为最好结果.
Abstract
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.
关键词
Keywords
references
Eppstein D.Finding the ksmallest spanning trees[J].BIT,1992,32: 237-248.
Shen X,Liang W.A parallel algorithm for multiple edge undates of minimum spanning trees[J].Proc 7th Internat Parallel Processing Symp,1993,310-317.
Ho J H,Lee D T,Chang C H,Wong C K.Minimum diameter spanning trees and related problems[J].SIAM J Comput,1991,20: 987-997.
Camerini P M.The min-max spanning tree problem and some extensions[J].Inform Process Lerr,1978,7(1): 10- 14.
Chen W T,Huang N F.The strongly connecting problem on multihop packet radio networks[J].IEEE Trans Comm,1989,37(3): 293-295.
Broersma H J,Li X.Spanning trees with many or few colors in edge-colored graphs[J].Discussiones Mathematicae Graph Theory,1997,17(2): 259-269.
Chang R S,Leu S J.The minimum labeling spanning trees[J].Inform Process Lett,1997,63: 277-282.
Krumke S O,Wirth H C.On the minimum label spanning tree problem[J].Inform.Process Lett,1998,66(2): 81- 85.
Xiong Y P,Golden B,Wasil E.Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem[J].Operations Research Letters,2005,33: 77-80.
Garey M R.Johnson D S.Computers and Intractability,A guide to the theory of NP-completeness[M].New York: W H Freeman and Company,1979.
Papadimitriou C H,Steiglitz K.Combinatorial Optimization: Algorithms and Complexity[M].Prentice-Hall,Inc, New Jersey,1982.
京公网安备11010802024621