|
|||||
|
|
| 网络中支撑树的边扩容问题 | |
| 引用本文： | 朱娟萍,吴旭亭,杨子兰.网络中支撑树的边扩容问题[J].云南大学学报(自然科学版),2013(5):592-597. |
| 作者姓名： | 朱娟萍 吴旭亭 杨子兰 |
| 作者单位： | 云南大学数学系;云南大学旅游文化学院信息科学与技术系 |
| 基金项目： | 国家自然科学基金(11126355,61063011) |
| 摘 要： | 受多种网络改进模型的启发,作者研究了网络中支撑树的边扩容问题(GECAT).证明了GECAT问题和限制性最小支撑树问题是多项式等价的,从而说明GECAT是NP-难的.由GECAT问题到限制性最小支撑树问题的等价归约构造方式,得到一个多项式时间近似方法(PTAS).接下来,对GECAT问题的2种特殊形式做了研究并分别给出了强多项式时间算法:支撑树上需扩容边的数目最少问题和最小支撑树所需的扩容费用最少问题.对于前者,采用了T-交换算法,而后者则采用了字典序法. |
| 关 键 词： | 支撑树 边扩容 强多项式算法 T-交换 字典序 |
| 本文献已被 CNKI 等数据库收录！ | |
