最小最大路划分的一个启发式算法

A heuristic algorithm for path partition of edge-weighted graphs

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.

The problem of min-max k-path partition was considered. The NP-hardness of the problem was proved. An optimal algorithm for special cases was constructed by binary search method. A heuristic algorithm was presented for completed graphs with triangle inequality by the same idea.