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

作     者：郭龙坤 沈鸿 GUO Long-kun;SHEN Hong

作者机构：中国科学技术大学计算机科学与技术学院合肥230026 北京交通大学计算机与信息技术学院北京100044 

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

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2012年第33卷第9期

页      码：1992-1996页

摘      要：随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想.

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1000-1220.2012.09.024

馆 藏 号：203365381...