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

Algorithms for some cases of group and covering Steiner problems

作　　者：王继强[1,2] 

机构地区：[1]山东大学数学与系统科学学院 [2]山东财政学院数理与统计学院,济南250014

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

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

摘　　要：综合论述了理论计算机科学领域中两个密切相关的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.

关 键 词：分组Steiner问题 覆盖Steiner问题 近似算法 

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