关于Steiner网络设计问题的近似算法综述  

Survey on Approximation Algorithms on the Steiner Network Problem

作　　者：郭龙坤[1] 沈鸿[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230026 [2]北京交通大学计算机与信息技术学院,北京100044

出　　处：《小型微型计算机系统》2012年第9期1992-1996,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60772034)资助

摘　　要：随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想.Along with the rapid development of network communication technology and the explosive growth of the internet applica- tions, network reliability is attracting more and more attention, because of its applications in both traditional areas such as defense, fi- nance and power industry, and emerging areas such as trusted computing, cloud computing and next-generation Internet. The topic of improving network reliability based on network topology while minimizing network resource usage is attracting considerable research interest. The well-known minimum Steiner network problem, as a basic problem within this topic has been well studied. In this pa- per, we survey the existing approximation algorithms for the minimum Steiner network problem.

关 键 词：连通度 Steiner网络 近似算法 线性规划 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]