| 瓶颈Steiner网络设计问题的算法研究 |
| |
| 引用本文： | 王继强,李国君.瓶颈Steiner网络设计问题的算法研究[J].计算机工程,2008,34(4):125-126. |
| |
| 作者姓名： | 王继强 李国君 |
| |
| 作者单位： | 1. 山东大学数学与系统科学学院,济南,250100;山东财政学院统计与数理学院,济南250014
2. 山东大学数学与系统科学学院,济南,250100 |
| |
| 摘 要： | 瓶颈Steiner网络设计问题要求从网络中找出一个满足某种瓶颈条件的Steiner树，由于该问题的NP困难性，因此必须找出它的近似算法。该文针对树和一般图这2种网络情形，在问题转化的基础上分别给出了基于分组Steiner问题的近似算法，在Marathe等算法思想的基础上给出了有根和无根2种情形下的2个近似算法。
|
| 关 键 词： | 网络设计 瓶颈 分组Steiner 最小比权圈 近似算法 |
| 文章编号： | 1000-3428（2008）04-0125-02 |
| 收稿时间： | 2007-03-28 |
| 修稿时间： | 2007年3月28日 |
Research of Algorithms for Bottleneck Steiner Network Design Problem |
| |
| WANG Ji-qiang,LI Guo-jun.Research of Algorithms for Bottleneck Steiner Network Design Problem[J].Computer Engineering,2008,34(4):125-126. |
| |
| Authors: | WANG Ji-qiang LI Guo-jun |
| |
| Affiliation: | (1. School of Math. and System Science, Shandong University, Jinan 250100;2. College of Statistics and Math., Shandong Finance Institute, Jinan 250014) |
| |
| Abstract: | Bottleneck Steiner network design problem intends to find a Steiner tree in a network that satisfies some bottleneck constraint. The NP-hardness of this problem makes it inevitable to look for its approximation algorithms. Based on the group Steiner problem, two approximation algorithms are presented for the tree and the general graph cases of networks. Two approximation algorithms for the rooted and the unrooted cases are proposed on the basis of the algorithmic idea of Marathe et al. |
| |
| Keywords: | network design bottleneck group Steiner minimum-ratio weight cycle approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
