您当前的位置: > 详细浏览

An efficient implementation for solving the all pairs minimax path problem in an undirected dense graph

请选择邀稿期刊:
摘要: We provide an efficient $ O(n^2) $ implementation for solving the all pairs minimax path problem or  widest path problem in an undirected dense graph. It is a code implementation of the Algorithm 4 (MMJ distance by Calculation and Copy) in a previous paper. The distance matrix is also called the all points path distance (APPD). We conducted experiments to test the implementation and algorithm, compared it with several other algorithms for solving the APPD matrix.  Result shows Algorithm 4 works good for solving the widest path or minimax path APPD matrix.  It can drastically improve the efficiency for computing the APPD matrix.  There are several theoretical outcomes which claim the APPD matrix can be solved accurately in $ O(n^2) $ . However, they are impractical because there is no code implementation of these algorithms. It seems Algorithm 4 is the first algorithm that has an actual code implementation for solving the APPD matrix of minimax path or widest path problem in $ O(n^2) $, in an undirected dense graph.

版本历史

[V2] 2024-07-09 10:03:46 ChinaXiv:202407.00106V2 下载全文
[V1] 2024-07-09 01:21:50 ChinaXiv:202407.00106v1 查看此版本 下载全文
点击下载全文
预览
同行评议状态
待评议
许可声明
metrics指标
  •  点击量118
  •  下载量28
评论
分享
申请专家评阅