An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
复制标题
DOI：
10.1287/ijoc.5.4.426
复制
发表时间：
1993-11
期刊：
影响因子：
--
通讯作者：
M. Fischetti;P. Toth
中科院分区：
文献类型：
--
作者：
M. Fischetti;P. Toth
提出了一种求解完全有向图中根顶点固定的最小和树状问题的有效算法。该算法基于著名的埃德蒙兹方法。新方法利用简单的数据结构，从而改善计算时间和内存需求。通过使用基于稀疏问题解决方案的新算法，获得了进一步的改进。还计算了与弧相关的线性规划降低的成本。描述了 FORTRAN 实现；作者可根据要求提供相应的代码。给出了真实世界和随机实例的广泛计算结果，显示了所提出算法的有效性。 INFORMS 计算杂志，ISSN 1091-9856，从 1989 年到 1995 年以 ORSA 计算杂志出版，ISSN 0899-1499。
An efficient algorithm for the solution of the Min-Sum Arborescence Problem with fixed root-vertex in complete digraphs is presented. The algorithm is based on the well-known Edmonds method. The new approach makes use of simple data structures leading to improvements affecting both computing times and memory requirements. Further improvements are obtained by using a new algorithm based on the solution of a sparse problem. The linear programming reduced costs associated with the arcs are also computed. A FORTRAN implementation is described; the corresponding code is available, on request, from the authors. Extensive computational results on both real-world and random instances are given, showing the effectiveness of the proposed algorithms. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.