A parallel algorithm is described for computing the minimum spanning tree of an undirected, connected and weighted graph withn vertices. We assume a shared-memory single-instruction-stream, multiple-data-stream model ...
详细信息
A parallel algorithm is described for computing the minimum spanning tree of an undirected, connected and weighted graph withn vertices. We assume a shared-memory single-instruction-stream, multiple-data-stream model of computation which does not allow read or write conflicts. The algorithm is adaptive in the sense that it usesn 1−e processors and runs inO(n 1+e ) time wheree lies between 0 and 1 and depends on the number of available processors. In view of the obvious Ω(n 2) lower bound on the number of operations required to compute a minimum spanning tree, the algorithm is also cost-optimal.
Given a sequence of n ordered but not sorted b-bit integers, an algorithm is described to select the k th smallest by reducing the length of the original sequence until only the required k th value or those equal to t...
详细信息
Given a sequence of n ordered but not sorted b-bit integers, an algorithm is described to select the k th smallest by reducing the length of the original sequence until only the required k th value or those equal to the k th remain. Using the time to add two bits as the unit, a running time of O(b log n) is obtained by employing O(n) simple processors arranged in a binary tree. The algorithm is then adapted to run on a binary tree of processors with N leaves, where N log N ⩽ n, in O(bn/N) time for an optimalcost of O(bn).
A parallel algorithm for generating all combinations ofm out ofn items in lexicographic order is presented. The algorithm usesm processors and runs inO(nCm) time. The cost of the algorithm, which is the parallel runni...
详细信息
A parallel algorithm for generating all combinations ofm out ofn items in lexicographic order is presented. The algorithm usesm processors and runs inO(nCm) time. The cost of the algorithm, which is the parallel running time multiplied by the number of processors used, is optimal to within a constant multiplicative factor in view of the Ω(ncm*m) lower bound on the number of operations required to solve this problem using a sequential computer.
暂无评论