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.展开更多
In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is sho...In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.展开更多
文摘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.
基金Research supported by the Science Foundation of Shandong Province.
文摘In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.
