| 求解区域网络问题的近似算法 |
| |
| 引用本文： | 陈静,胥小庆,唐恒永.求解区域网络问题的近似算法[J].沈阳航空工业学院学报,2007,24(2):82-84. |
| |
| 作者姓名： | 陈静 胥小庆 唐恒永 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 区域网络是给定一个无向图G=(V,E),在图G中,存在一个子图是森林,森林中的若干个不相交的树称为若干个区域。该问题的目标是把该森林子图即若干个区域连结成一棵树,且使增加的边的权和最小。把该问题归结为图的Steiner tree问题,给出了求解该问题的一个近似算法,并证明其复杂性,最后用实例说明算法的准确性。
|
| 关 键 词： | 区域网络 Steiner tree问题 近似算法 算法复杂性 |
| 文章编号： | 1007-1385（2007）02-0082-03 |
| 收稿时间： | 2006-11-03 |
| 修稿时间： | 2006-11-03 |
An approximation algorithm about regional networks problem |
| |
| CHEN Jing,XU Xiao-qing,TANG Heng-yong.An approximation algorithm about regional networks problem[J].Journal of Shenyang Institute of Aeronautical Engineering,2007,24(2):82-84. |
| |
| Authors: | CHEN Jing XU Xiao-qing TANG Heng-yong |
| |
| Institution: | College of Mathematics and Systems Science,Shenyang Normal University, Liaoning Shenyang 110034 |
| |
| Abstract: | Suppose that there is a graph,and containing a sub-graph which is a forest in G,some connected branches in the forest are named Regionals.Regional networks problem is to find the shortest connection to connect the forest to be a tree along pre-existing networks.In the text,we change the problem to the Steiner tree problem in graph,and give out an approximation algorithm and proved the algorithm complexity of this problem.In the last,we show the algorithm accuracy with an example. |
| |
| Keywords: | regional networks Steiner tree problem approximation algorithm algorithm complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
