An O(log n) time, n processor randomized algorithm for computing the k-nearest neighbor graph of n points in d dimensions, for fixed d and k is presented. the method is based on the use of sphere separators. Probabili...
详细信息
ISBN:
(纸本)089791483X
An O(log n) time, n processor randomized algorithm for computing the k-nearest neighbor graph of n points in d dimensions, for fixed d and k is presented. the method is based on the use of sphere separators. Probability bounds are proved using the moment generating function technique.
A new approach to parallel sorting called parallel Sorting by OverPartitioning (PSOP) is presented. the approach limits the communication cost by moving each element between processors at most once, and leads to good ...
详细信息
We present an algorithm that computers a minimum spanning tree (MST) of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log3/2 n) time using n + m processors. this re...
详细信息
ISBN:
(纸本)089791483X
We present an algorithm that computers a minimum spanning tree (MST) of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log3/2 n) time using n + m processors. this represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.
A novel extension to external double hashing providing significant reduction to both successful and unsuccessful search lengths is presented. the experimental and analytical results demonstrate the reductions possible...
详细信息
ISBN:
(纸本)0769525091
A novel extension to external double hashing providing significant reduction to both successful and unsuccessful search lengths is presented. the experimental and analytical results demonstrate the reductions possible. this method does not restrict the hashing table configuration parameters and utilizes very little additional storage space per bucket. the runtime performance for insertion is slightly greater than for ordinary external double hashing.
Using the ideas from the NC algorithm of Ben-Or and Tiwari [Journal of Complexity 6, 417-442, 1990], we develop a practical parallel algorithm that approximates the roots of a polynomial whose roots are all real. A ne...
详细信息
ISBN:
(纸本)089791483X
Using the ideas from the NC algorithm of Ben-Or and Tiwari [Journal of Complexity 6, 417-442, 1990], we develop a practical parallel algorithm that approximates the roots of a polynomial whose roots are all real. A new elementary proof of correctness is provided and the complexity of the algorithm is analyzed. A particular implementation of the algorithm that performs well in practice is described and its run-time behaviour is compared withthe analytical predictions. Its performance is also compared withthat of the root-finding algorithm in the PARI package.
We present parallelalgorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, lo...
详细信息
ISBN:
(纸本)089791483X
We present parallelalgorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CRCW PRAM, f(n) is o(n3). On the randomized CRCW PRAM we are able to achieve time complexity O(n3/p + log n) using p processors.
暂无评论