| 逆一般中心选址问题的算法研究 |
| |
| 引用本文： | 李淑君,唐恒永. 逆一般中心选址问题的算法研究[J]. 系统工程, 2006, 24(2): 113-117 |
| |
| 作者姓名： | 李淑君 唐恒永 |
| |
| 作者单位： | 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 主要讨论了逆一般中心选址问题的算法研究。对于实例是树且U为整数的情况,逆一般中心选址问题转化为逆中心选址问题。对于实例是一般简单图的情况,本文给出了一个逆一般中心选址问题转化为权重为1的S te iner树问题的拟多项式算法。并对于权w=1的S te iner树问题,本文也给出了一个近似界为43的近似算法。
|
| 关 键 词： | 逆一般中心选址问题 拟多项式算法 Steiner树 近似算法 |
| 文章编号： | 1001-4098（2006）02-0113-05 |
| 收稿时间： | 2005-11-12 |
| 修稿时间： | 2005-11-12 |
A Study of Algorithm for the Reverse General Center Location |
| |
| LI Shu-jun,TANG Heng-yong. A Study of Algorithm for the Reverse General Center Location[J]. Systems Engineering, 2006, 24(2): 113-117 |
| |
| Authors: | LI Shu-jun TANG Heng-yong |
| |
| Abstract: | We discuss the study of algorithm for the reverse general center location problem.For the case being a tree and being an integer,the reverse general center location problem can be transformed to the reverse center location problem.As to the general graph case,we give an pseudopolynomial algorithm to transform the reverse general center location problem into the Steiner tree with unit weight problem.For the Steiner tree with unit weight problem,we also give afactor approximation algorithm. |
| |
| Keywords: | Reverse General Center Location Problem t Steiner Tree pseudopolynomial Algorithm Approximation Algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
