文献类型：期刊文章

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

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

出　　处：《云南大学学报（自然科学版）》

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

年　　份：2013

卷　　号：35

期　　号：5

起止页码：592-597

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CAB、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2013_2014、IC、JST、MR、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：受多种网络改进模型的启发,作者研究了网络中支撑树的边扩容问题(GECAT).证明了GECAT问题和限制性最小支撑树问题是多项式等价的,从而说明GECAT是NP-难的.由GECAT问题到限制性最小支撑树问题的等价归约构造方式,得到一个多项式时间近似方法(PTAS).接下来,对GECAT问题的2种特殊形式做了研究并分别给出了强多项式时间算法:支撑树上需扩容边的数目最少问题和最小支撑树所需的扩容费用最少问题.对于前者,采用了T-交换算法,而后者则采用了字典序法.

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

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