Packing cycles exactly in polynomial time
Let G = (V, E) be an undirected graph in which every vertex v. V is assigned a nonnegative integer w(v). A w- packing is a collection P of cycles (repetition allowed) in G such that every v. V is contained at most w(v) times by the members of P. Let   = 2|V | + Sigma(v is an element of V)[log(w(v)+ 1)] denote the binary encoding length (input size) of the vector (w(v): v is an element of V)(T). We present an efficient algorithm which finds in O(|V|(8)  (2) + |V|(14)) time a w- packing of maximum cardinality in G provided packing and covering cycles inGsatisfy the Z(+)-max-flow min-cut property.
packing and covering polynomial algorithm min-max relation maximum cycle packing