• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Indian Journal of Science and Technology >Comparative Analysis of Some Modified Prim’s Algorithms to Solve the Multiperiod Degree Constrained Minimum Spanning Tree Problem
【24h】

Comparative Analysis of Some Modified Prim’s Algorithms to Solve the Multiperiod Degree Constrained Minimum Spanning Tree Problem

机译：解决多周期约束最小生成树问题的某些改进Prim算法的比较分析

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Objectives: To compare the WAC1, WAC2, and WAC3 algorithms against WADR1, WADR2, WADR3, WADR4, and WADR5 algorithms to solve the Multiperiod Degree Constrained Minimum Spanning Tree. Methods/Statistical analysis: WAC1, WAC2, and WAC3 are algorithms developed by modifying Prim’s algorithm for the Minimum Spanning Tree (MST) and adopting the period of installation/connecting for vertices in the network. In WAC1, WAC2, and WAC3 algorithms we consider the HVTk, the set of vertices that must be connected on kth period, while in WADR5 is not. In WAC1 the vertices in HVTkmust be installed as early as possible, while in WAC2 is not given priority to be connected as soon as possible, but can be any time as long as the connection still on that current period. In WAC3, we adopt the smallest value for 2-path for vertex under consideration to be connected. All algorithm proposed used the same data as used in WADR1, WADR2,WADR3, WADR4 and WADR5. Findings: Since WAC1, WAC2, and WAC3, WADR5 algorithms are based on modified Prim’s algorithm, then the connectivity property is maintained during the process of installation/connection not like WADR1, WADR2, WADR3, and WADR4 where based on kruskal’s. Based on the same data used and connectivity property, the result shows that the performance of WAC2 is the best among the other algorithms developed. Application/Improvements: Considering real life application in the network installation problem, the WAC2 algorithm is one of alternative solutions since it maintains connectivity property and performs best.
机译：目的：比较WAC1，WAC2和WAC3算法与WADR1，WADR2，WADR3，WADR4和WADR5算法，以求解多周期度约束的最小生成树。方法/统计分析：WAC1，WAC2和WAC3是通过修改最小生成树（MST）的Prim算法并采用网络中顶点的安装/连接时间段开发的算法。在WAC1，WAC2和WAC3算法中，我们考虑了HVTk，这是在第k个周期必须连接的一组顶点，而在WADR5中则不是。在WAC1中，必须尽早安装HVT中的顶点，而在WAC2中，不优先考虑尽快连接，但可以保持任何时间，只要该连接仍在当前时间段内即可。在WAC3中，对于要连接的顶点，我们采用2路径的最小值。建议的所有算法都使用与WADR1，WADR2，WADR3，WADR4和WADR5中使用的数据相同的数据。结果：由于WAC1，WAC2和WAC3，WADR5算法是基于改良的Prim的算法，因此在安装/连接过程中保持了连接属性，这与基于kruskal的WADR1，WADR2，WADR3和WADR4不同。基于所使用的相同数据和连接性，结果表明WAC2的性能是其他开发算法中最好的。应用程序/改进：考虑到网络安装问题中的实际应用，WAC2算法是一种替代解决方案，因为它保持了连接性并且性能最佳。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号