计算机工程 ›› 2008, Vol. 34 ›› Issue (4): 125-126.doi: 10.3969/j.issn.1000-3428.2008.04.043

• 网络与通信 • 上一篇    下一篇

瓶颈Steiner网络设计问题的算法研究

王继强1,2,李国君1   

  1. (1. 山东大学数学与系统科学学院,济南 250100;2. 山东财政学院统计与数理学院,济南250014)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20

Research of Algorithms for Bottleneck SteinerNetwork Design Problem

WANG Ji-qiang1,2, LI Guo-jun1   

  1. (1. School of Math. and System Science, Shandong University, Jinan 250100;2. College of Statistics and Math., Shandong Finance Institute, Jinan 250014)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20

摘要: 瓶颈Steiner网络设计问题要求从网络中找出一个满足某种瓶颈条件的Steiner树,由于该问题的NP困难性,因此必须找出它的近似算法。该文针对树和一般图这2种网络情形,在问题转化的基础上分别给出了基于分组Steiner问题的近似算法,在Marathe等算法思想的基础上给出了有根和无根2种情形下的2个近似算法。

关键词: 网络设计, 瓶颈, 分组Steiner, 最小比权圈, 近似算法

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.

Key words: network design, bottleneck, group Steiner, minimum-ratio weight cycle, approximation algorithm

中图分类号: