In this paper we describe a technique for finding efficient parallelalgorithms for problems on directed graphs that involve checking the ezistence of certain kinds of paths in the graph. This technique provides effic...
详细信息
We present parallelalgorithms for several graph and geometric problems, including transitive closure and topological sorting in planar st-graphs, preprocessing planar subdivisions for point location queries, and cons...
详细信息
We give an efficient parallel algorithm for constructing the arrangement of n line segments in the plane, i.e., the planar graph 'determined by the segment endpoints and intersections. Our algorithm is efficient r...
详细信息
An HMM is a very simple parallel machine consisting of finite state devices that can manipulate pointers to each other. The more commonly studied PRAM is a much richer parallel machine with a shared global memory and ...
Let (G) denote the independence number of a graph G, that is the maximum number of pairwise independent vertices in G. We present a parallel algorithm that computes in a planar graph G = (V, E), an independent set I ⊂...
详细信息
The PRAM model of parallel computation is examined with respect to wordsize, the number of bits which can be held in each global memory cell. First, adversary arguments are used to show the incomparability of certain ...
详细信息
Let T be a collection of data templates of an N × N matrix, T = {row, column, forward diagonal, backward diagonal}. In the context of parallel processing, the question of whether it is possible or not for a paral...
详细信息
We show that the several problems, whose complexity with respect P and NC was open, are equivalent under NC-reductions. These include: (1) Finding the optimal solution of a two-variable integer program;(2) Determining...
详细信息
We present parallelalgorithms for evaluating game trees. These algorithmsparallelize the "left-To-right" sequential algorithm for evaluating AND]OR trees and the α-β pruning procedure for evaluating MIN/...
详细信息
A family of VLSI architectures for computing an (n 1 × n 2 × • • " × nd)-point multidimensional D1VF (MDDFT) over Zm, the ring of integers modulo M, is presented. These architectures achieve VLSI a...
详细信息
暂无评论