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

Research of Algorithms for Bottleneck Steiner Network Design Problem

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

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.