网络中支撑树的边扩容问题  

Edge capacity augmentation problem on spanning trees in networks

作　　者：朱娟萍[1] 吴旭亭[1] 杨子兰 

机构地区：[1]云南大学数学系,云南昆明650091 [2]云南大学旅游文化学院信息科学与技术系,云南丽江674100

出　　处：《云南大学学报（自然科学版）》2013年第5期592-597,共6页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金(11126355;61063011)

摘　　要：受多种网络改进模型的启发,作者研究了网络中支撑树的边扩容问题(GECAT).证明了GECAT问题和限制性最小支撑树问题是多项式等价的,从而说明GECAT是NP-难的.由GECAT问题到限制性最小支撑树问题的等价归约构造方式,得到一个多项式时间近似方法(PTAS).接下来,对GECAT问题的2种特殊形式做了研究并分别给出了强多项式时间算法:支撑树上需扩容边的数目最少问题和最小支撑树所需的扩容费用最少问题.对于前者,采用了T-交换算法,而后者则采用了字典序法.Motivated by various network improvement models, we study the general edge capacity augmenta- tion problem on spanning trees in networks （GECAT）. The polynomial equivalence between the GECAT problem and the constrained minimum spanning tree problem （CST） is presented,which indicates the GECAT problem is NP - hard. By transforming the GECAT problem into an instance of the CST problem, a polynomial - time approx- imation scheme （PTAS） is designed to solve the GECAT problem. Two special versions of the GECAT problem are studied：the minimum number of edges to be augmented on spanning trees （MNEAT） and the minimum -cost edge capacity augmentation on minimum spanning trees （MCEAT）. A strongly polynomial - time algorithm is de- signed for each version. For the MNEAT problem, the T - exchange method is used on the spanning trees. For the MCEAT problem, the lexicographical order strategy is utilized.

关 键 词：支撑树 边扩容 强多项式算法 T-交换 字典序 

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