An efficient parallel algorithm for testing whether a graph G is k-vertex connected is presented. The algorithm runs in O(k2 log n) time and uses (n + k2)kC(n, m) processors on a CRCW PRAM, where n and m are the numbe...
详细信息
An efficient parallel algorithm for testing whether a graph G is k-vertex connected is presented. The algorithm runs in O(k2 log n) time and uses (n + k2)kC(n, m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of G, and C(n, m) is the number of processors required to compute the connected components of G in logarithmic time. For fixed k, the algorithm runs in logarithmic time and uses nC(n, m) processors. To develop our algorithm, an efficient parallel algorithm is designed for the following disjoint s-t paths problem. Given a graph G, and two specified vertices s and t, find k vertex disjoint paths between s and t, if they exist. If no such paths exist, find a set of at most k-1 vertices whose removal disconnects s and t. The parallel algorithm for this problem runs in O(k2 log n) time and uses kC(n, m) processors. The way to modify the algorithm to find k-edge disjoint paths, if they exist, is shown. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected. The algorithm runs in O(k2 log n) time and uses nkC(n, kn) processors on a CRCW PRAM. Finally, more applications of the disjoint s-t paths algorithm are described.
This paper presents efficient and portable implementations of a useful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique which makes use of the SNF and a variant o...
详细信息
This paper presents efficient and portable implementations of a useful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique which makes use of the SNF and a variant of the conventional connected components algorithm which we call δ-Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations.) Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.
parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm....
详细信息
Redundancy is a basic technique for achieving fault tolerance, but the overhead introduced by redundancy may degrade system's performance. In this paper, we propose efficient replication based algorithms for fault...
详细信息
Floorplan design is the first task in VLSI layout and perhaps the most important one. It is the problem of allocating space to a set of modules in the plane in order to minimize the area of the bounding rectangle. The...
详细信息
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blo...
详细信息
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blockwise communication, and use Valiant's notion of 1-optimality. Intuitively, a 1-optimal parallel algorithm for p processors achieves speed-up close to p. We consider the Multisearch Problem: Assume a strip in 2D to be partitioned into m segments. Given n query points in the strip, the task is to locate, for each query, its segment. For m less than or equal to n greater than or equal to p we present a deterministic BSP* algorithm that is 1-optimal, if n/p greater than or equal to log(2)n. For m>n greater than or equal to p, we present a randomized BSP* algorithm that is 1-optimal with high probability, if m less than or equal to 2(p) and n/p greater than or equal to log(3)n. Both results hold for a wide range of BSP* parameters where the range becomes larger with growing input size n. We further report on implementation work. Previous parallel algorithms for Multisearch were far away from being 1-optimal in our model and did not consider blockwise communication. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
In this paper: we present rounding error bounds of recent parallel versions of Forsythe's and Clenshaw's algorithms for the evaluation of finite series uf Chebyshev polynomials of the first and second kind. Th...
详细信息
In this paper: we present rounding error bounds of recent parallel versions of Forsythe's and Clenshaw's algorithms for the evaluation of finite series uf Chebyshev polynomials of the first and second kind. The backward errors are studied by using the matrix formulation of the algorithm, whereas the forward error is also Studied by means of a more direct approach that permits us to obtain sharper bounds. The bounds show all almost stable behavior as ill the sequential algorithms. This fact is: illustrated with several numerical tests. (C) 2001 Elsevier Science Ltd. All rights reserved.
An edge is a bisector of a simple path if it contains the middle point of the path. Let T = (V, E) be a tree. Given a source vertex s is an element of V, the single-source tree bisector problem is to find, for every v...
详细信息
An edge is a bisector of a simple path if it contains the middle point of the path. Let T = (V, E) be a tree. Given a source vertex s is an element of V, the single-source tree bisector problem is to find, for every vertex v is an element of V, a bisector of the simple path from s to v. The all-pairs tree bisector problem is to find for, every pair of vertices u, v is an element of V, a bisector of the simple path from u to v. In this paper, it is first shown that solving the single-source tree bisector problem of a weighted tree has a time lower bound Omega (n log n) in the sequential case. Then, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and is for unweighted trees. The other uses O(n log n) work and is for weighted trees. Previous algorithms for the single-source problem could achieve the same time O(log n) and the same optimal work, O(n) for unweighted trees and O(n log n) for weighted trees, on the CRCW PRAM. The contribution of our single-source algorithms is the improvement from CRCW to EREW. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n(2)) work. All the proposed algorithms are cost-optimal. Efficient tree bisector algorithms have practical applications to several location problems on trees. Using the proposed algorithms, efficient parallel solutions for those problems are also presented.
When dealing with high-frequency time series, statistical procedures giving reliable estimates of unknown parameters and forecasts in real time are required. This is why recursive estimation methods are usually prefer...
详细信息
When dealing with high-frequency time series, statistical procedures giving reliable estimates of unknown parameters and forecasts in real time are required. This is why recursive estimation methods are usually preferred to maximum-likelihood estimators. In the paper, a recursive estimation algorithm for the system parameter of dynamic linear models is proposed. A comparison with some other algorithms is given via Monte Carlo simulations. Consistency properties of the algorithms are also empirically verified. Copyright (C) 1999 John Wiley & Sons, Ltd.
作者：
REISCHUK, RUniv Bielefeld
Fakultaet fuer Mathematik Bielefeld West Ger Univ Bielefeld Fakultaet fuer Mathematik Bielefeld West Ger
Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes wit...
详细信息
Probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes with high probability in constant time and the sorting tree in time O(logn)
暂无评论