Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
Let X be the vertex set of Kn. A k-cycle packing of Kn is a triple （X, C, L）, where C is a collection of edge disjoint k-cycles of Kn and L is the collection of edges of Kn not belonging to any of the k-cycles in C....Let X be the vertex set of Kn. A k-cycle packing of Kn is a triple （X, C, L）, where C is a collection of edge disjoint k-cycles of Kn and L is the collection of edges of Kn not belonging to any of the k-cycles in C. A k-cycle packing （X, C, L） is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of Kn, denoted by k-RMCP（n）, is a resolvable k-cycle packing of Kn, （X, C, L）, in which the number of almost parallel classes is as large as possible. Let D（n, k） denote the number of almost parallel classes in a k-RMCP（n）. D（n, k） for k = 3, 4 has been decided. When n ≡ k （mod 2k） and k ≡1 （mod 2） or n ≡1 （mod 2k） and k e {6, 8, 10, 14} U{m： 5 ≤ m ≤ 49, m ≡1 （mod 2）}, D（n,k） also has been decided with few possible exceptions. In this paper, we shall decide D（n, 5） for all values of n ≥ 5.展开更多
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘Let X be the vertex set of Kn. A k-cycle packing of Kn is a triple （X, C, L）, where C is a collection of edge disjoint k-cycles of Kn and L is the collection of edges of Kn not belonging to any of the k-cycles in C. A k-cycle packing （X, C, L） is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of Kn, denoted by k-RMCP（n）, is a resolvable k-cycle packing of Kn, （X, C, L）, in which the number of almost parallel classes is as large as possible. Let D（n, k） denote the number of almost parallel classes in a k-RMCP（n）. D（n, k） for k = 3, 4 has been decided. When n ≡ k （mod 2k） and k ≡1 （mod 2） or n ≡1 （mod 2k） and k e {6, 8, 10, 14} U{m： 5 ≤ m ≤ 49, m ≡1 （mod 2）}, D（n,k） also has been decided with few possible exceptions. In this paper, we shall decide D（n, 5） for all values of n ≥ 5.
