若干情形分组和覆盖Steiner问题的算法

Algorithms for some cases of group and covering Steiner problems

下载PDF

导出

摘要综合论述了理论计算机科学领域中两个密切相关的NP-困难问题:分组Steiner问题和覆盖Steiner问题的不同解决途径,并就其若干特殊情形设计了近似比更好的近似算法。 We review different avenues to solve two closely-related NP-hard problems in theoretical computer science,the group Steiner problem and the covering Steiner problem,and design improved approximation algorithm for some special cases of them.

作者王继强

机构地区山东大学数学与系统科学学院山东财政学院数理与统计学院

出处《计算机工程与应用》 CSCD 北大核心 2007年第18期30-31,共2页 Computer Engineering and Applications

基金国家自然科学基金(the National Natural Science Foundation of China under Grant No.60373025) 。

关键词分组Steiner问题覆盖Steiner问题近似算法 group Steiner problem covering Steiner problem approximation algorithm

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

引文网络
相关文献

参考文献8

1Ihler E.The complexity of approximating the class Steiner tree problem[C]//LNCS 570:Graph-Theoretic Concepts in Computer Science WG91,Springer,1992:85-96.
2Konjevod G,Ravi R,Srinivasan A.Approximation algorithms for the covering Steiner problem[J].Random Structures and Algorithms(Special Issue on Probabilistic Methods in Combinatorial Optimization),2002,20 (3):465 -482.
3Garg N,Konjevod G,Ravi R.A polylogarithmic approximation algorithm for the group Steiner problem[J].Journal of Algorithms,2000,37 (1):66-84.
4Garg N.Saving an epsilon:a 2-approximation algorithm for the k-mst problem in graphs[C]//Proceedings of the 37th Annual ACM Symposium on Theory of Computing,2005:396-402.
5Robins G,Zelikovsky A.Improved Steiner tree approximation in graphs[C]//Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms,2000:770-779.
6Bartal Y.On approximating arbitrary metrics by tree metrics[C]//Proceedings of the 30th Annual ACM Symposium on Theory of Computing,1998:161-168.
7Bartal Y.Probabilistic approximation of metric spaces and its algorithmic applications[C]//Proceedins of the 37th Annual IEEE Symposium on Foundations of Computer Science,1996:184-193.
8Fakcharoenphol J,Rao S,Talwar B.A tight bound on approximating arbitrary metrics by tree metrics[C]//Proceedings of the 35th Annual ACM Symposium on Theory of Computing,2003:448-455.

1中国计算机学会理论计算机科学专业委员会简介[J].计算机与数字工程,2009,37(8).
2王飓安,李未.ELF 类型理论及其应用[J].计算机科学,1992,19(2):20-24.
32004年全国理论计算机科学学术年会征文通知[J].软件学报,2004,15(4):486-486.
4无.2009年全国理论计算机科学学术年会征文通知[J].计算机与数字工程,2009,37(2):198-198.
52007全国理论计算机科学学术年会征文通知[J].计算机研究与发展,2007,44(2):325-325.
62007全国理论计算机科学学术年会征文通知[J].计算机研究与发展,2006,43(12):2095-2095.
72004年全国理论计算机科学学术年会征文通知[J].软件学报,2004,15(3):359-359.
82007全国理论计算机科学学术年会征文通知[J].计算机研究与发展,2007,44(1):147-147.
92009年全国理论计算机科学学术年会征文通知[J].计算机工程与科学,2009,31(2):158-158.
102007全国理论计算机科学学术年会征文通知[J].计算机研究与发展,2007,44(3):433-433.

计算机工程与应用

2007年第18期

浏览历史

内容加载中请稍等...

若干情形分组和覆盖Steiner问题的算法

参考文献8

相关作者

相关机构

相关主题

浏览历史