摘要
建立了多参数最小支撑树问题 (RMST)的模型 ,并证明该问题是 NP-完全的。利用经典 Greedy算法 ,给出了该问题的一个近似算法 ,并分析了该近似算法的性能比 ,证明了所给出的界是紧的。
The model of minimum spanning tree with multiple parameter is established. It is proved that the problem is NP complete. Using the classical Greedy algorithm, a simple heuristic algorithm is given. Its bound is proved to be tight.
出处
《控制与决策》
EI
CSCD
北大核心
2000年第5期617-619,共3页
Control and Decision
基金
国家重点基础研究专项经费资助项目
