多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题 (RMST)的模型 ,并证明该问题是 NP-完全的。利用经典 Greedy算法 ,给出了该问题的一个近似算法 ,并分析了该近似算法的性能比 ,证明了所给出的界是紧的。

最小支撑树问题的三个算法

最小支撑树是指找图G的一棵权重最小的支撑树,探讨最小支撑树问题的三个算法(避圈法、破圈法、反圈法)及其时间复杂性,证明了反圈法的时间复杂性最优。

最小最大后悔支撑树问题

本文建立了最小最大后悔支撑树问题的模型 .利用划分问题 ,证明了该问题是 NP- C的 .然后利用两个已有的算法 ,给出了上下界估计 .最后对一种特殊情况 ,给出了一个启发式算法 。