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

李学良; 涂建华

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 次模函数近似算法求最小颜色生成树(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 112, Issue 4, Pages: 391-394(2008)
- 作者机构：
  
  南开大学组合数学中心
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2008
- 稿件说明：
移动端阅览
[1]李学良,涂建华.次模函数近似算法求最小颜色生成树(英文)[J].新疆大学学报(自然科学版),2008,No.112(04):391-394.

李学良, 涂建华. 次模函数近似算法求最小颜色生成树(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2008, 112(4): 391-394.
[1]李学良,涂建华.次模函数近似算法求最小颜色生成树(英文)[J].新疆大学学报(自然科学版),2008,No.112(04):391-394. DOI：

李学良, 涂建华. 次模函数近似算法求最小颜色生成树(英文)[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.

Simha R,Norahari B.Single path rounting with delay considerrations[J].Computer Network ISDN Systems,1992,24:405-419.

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰