寻找最大带宽的独立路径对算法

独立多路径算法在多径算法研究中具有重要地位。最小时延多路径问题的研究已较为成熟,而最大带宽多路径问题的研究却刚刚起步。文章介绍了有向图中链路独立路径对问题,提供了一种复杂度为O(mnlogn)求解该问题的多项式算法。该算法不需要考虑最大带宽链路独立路径对上流值分配问题,能够更好地应用到现实网络中。

关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究 ,尤其是在最近的网络 Qo S路由研究中的基本问题 .在以往的文献中 ,有人提出了利用修改的 Dijkstra算法或修改的 Bellm an- Ford算法来构建最大带宽路径 .该文给出了一个简单的证明 ,指出了最大生成树与最大带宽路径之间的特殊关系 ,证明了可以使用修改的 Kruskal算法来构建最大带宽路径 .文中给出了修改的 Kruskal算法 ,并且与已有的 Dijkstra算法作了性能上的比较 .尽管从理论上说 ,Dijstra算法和 Kruskal算法的时间复杂度具有同样的阶 ,但在多种不同网络结构上的模拟测试结果表明 ,用 Kruskal算法构建最大带宽路径的实际运行比 Dijkstra算法至少要快 3倍 ,而且在实现上比 Dijkstra算法更简单、灵活 .

关于实际构造最大带宽路径算法的研究

以往的研究中 ,已经提出了利用修改Dijkstra算法或修改Bellman -Ford算法来构建最大带宽路径 .本文证明可以使用修改的Kruskal算法来构建最大带宽路径 ,并且演示了该算法比前面提出的算法更为简单、灵活、快速且易于实现 .