关于图的最大圈装箱

On The Maximum Cycle-packing Preoblem of Weighted Graphs

本文给出了复杂性为O(|A|~3)的有向图的最大圈装箱问题的分配算法,从而证明了有向图上的最大圈装箱问题是P—问题。对于NP—完全的混合图上的最大圈装箱问题给出了分枝定界算法。

This paper gives an assignment algorithm with complexity O(|A|~3)for the maximum cycle-packing problem on weighted digraphs. Therefore,the maximum cycle- packing problem on weighted digraphs is a P-problem. For the maximum cycle-packing prob- les on weighted mixed graphs, a NP-complete problem, a branch-and-bound algorithm is given. This paper gives an assignment algorithm with complexity 0 (lA IS)for the maximum cycle-packing problem on weighted digraphs. Therefore t the maximum cycle- packing problem on weighted digraphs is a P-problem. For the max/mum cycle-packing prob- lem on weishted mixed sraphs, a NP-complete prob!em, a branch-and-bound algorithm is given.