Given a biconnected planar graph G and a pair of vertices s and t, the two disjoint problem asks to find a pair of internally disjoint paths from s to t. We present a simple and efficient parallel algorithm for the sa...
详细信息
Given a biconnected planar graph G and a pair of vertices s and t, the two disjoint problem asks to find a pair of internally disjoint paths from s to t. We present a simple and efficient parallel algorithm for the same. Our algorithm uses the notion of bridges in a novel way and this results in a more elegant and simple algorithm than the existing one. The all-bidirectional-edges (ABE) problem is to find an edge labeling such that an edge (u, v) in E is labeled [u, v] or [v, u] or both depending on the existence of a simple path from s to t that visits the vertices in the order u, v or v, u or both, respectively. We present an optimal parallel algorithm for the same.
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.
Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-con...
详细信息
Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-conquer, in which some simplest convex-hulls are generated first and then the final convex hull of all points is achieved by the processes of merging 2 sub-convex hulls. The second algorithm is by the process of picking up the points that are necessarily in the convex hull and discarding the points that are definitely not in the convex hull. Experimental results on a MIMD parallel system of 4 processors are analysed and presented.
In this paper, aimed at the neutron transport equations of eigenvalue problem under 2-D cylindrical geometry on unstructured grid, the discrete scheme of Sn discrete ordinate and discontinuous finite is built, and the...
详细信息
ISBN:
(纸本)9781627486439
In this paper, aimed at the neutron transport equations of eigenvalue problem under 2-D cylindrical geometry on unstructured grid, the discrete scheme of Sn discrete ordinate and discontinuous finite is built, and the parallel computation for the scheme is realized on MPI systems. Numerical experiments indicate that the designed parallel algorithm can reach perfect speedup, it has good practicality and scalability.
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...
详细信息
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.
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)
暂无评论