有向图上最大权圈装箱问题的有效算法  

An Efficient Algorithm for the Maximum Weighted Cycle Packing Problem on Digraphs

作　　者：杜林古[1] 

机构地区：[1]山东纺织工学院管理系

出　　处：《青岛大学学报（工程技术版）》1990年第1期75-80,共6页Journal of Qingdao University(Engineering & Technology Edition)

摘　　要：对弧赋权的有向图,其一组有向图称为图装箱,若其中任两个图无公共弧.有向图上最大权图装箱问题是:对任给的赋权有向图,找一图装箱,使所含弧的总权最大.本文给出了求解这一问题的多项式算法.Let D=(V,A)be a digraph with a weighted function defined on the are set A.A set of directed cycles in C={C_1,C_2,…,C_k}of D is called a cycle packing of D if any two distinct directed cycles in C are arc-disjoint.The maximum weighted cycle packing problem on digraphs is to find a cycle packing with the maximum total weight for a given weighted digraph.This paper describes a polynomial-time algorithm bounded by O(|V|~2·|A|)forit

关 键 词：有向图 有向■ ■装箱 有效算法 

分 类 号：TB-55[一般工业技术]