基于设施选址的Steiner问题的算法  

Algorithms Based on Facility Location for Steiner Problems

作　　者：王继强[1] 李国君[1] 

机构地区：[1]山东大学数学与系统科学学院

出　　处：《计算机科学》2007年第9期181-182,共2页Computer Science

基　　金：国家自然科学基金(10271065)资助

摘　　要：在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3.55和3.582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。As one kind of NP-hard optimization problem, the Steiner tree problem intents to find a minimum cost tree that satisfies some special requirement in an edge or vertex-weighted graph. Two approximation algorithms, based on the facility location problems,with approximation ratio 3. 55 and 3. 582, respectively, for the generalized Steiner treestar problem are presented. Additionally, approximation algorithms for some special cases of the Steiner tree problem are studied based on problems transformation.

关 键 词：Steiner树-星 设施选址 近似算法 问题转化 

分 类 号：O157.5[理学—数学]