A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined by Dymond and Tompa [J. Comput. System Sci., 30 (1985), pp. 149–161] and is used to char...
详细信息
A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined by Dymond and Tompa [J. Comput. System Sci., 30 (1985), pp. 149–161] and is used to characterize two natural parallel complexity classes, namely LOGCFL and ${\text{AC}}^1 $. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well-known results of complexity theory.
The complexity of the polynomial ideal membership problem over arbitrary fields within the framework of arithmetic networks is investigated. We prove that the parallel complexity of this problem is single exponential ...
详细信息
The complexity of the polynomial ideal membership problem over arbitrary fields within the framework of arithmetic networks is investigated. We prove that the parallel complexity of this problem is single exponential over any infinite field. Our lower bound is obtained by combining a modification of Mayr and Meyer's (1982) key construction with an elementary degree bound. (C) 1998 Academic Press, Inc.
We study the problem of computing canonical forms for graphs and hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of computing canonical form...
详细信息
We study the problem of computing canonical forms for graphs and hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of computing canonical forms for graphs to the problem of computing canonical forms for associated algebraic structures, and we develop parallel algorithms for these associated problems. 1. In our first result we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is logspace Turing equivalent to solving a system of linear equations over the field F-2. This implies a deterministic NC2 algorithm for the problem. 2. Similarly, we show that the problem of canonical labeling graphs and hypergraphs under arbitrary Abelian permutation group action is fairly well characterized by the problem of computing the integer determinant. In particular, this yields deterministic NC3 and randomized NC2 algorithms for the problem.
The problem of covering an acyclic directed graph (DAG) with node disjoint paths is discussed. Such a ''path cover'' is called ''maximal'' if the number of paths is minimum. The paralle...
详细信息
The problem of covering an acyclic directed graph (DAG) with node disjoint paths is discussed. Such a ''path cover'' is called ''maximal'' if the number of paths is minimum. The parallel computational complexity for the problem of finding a maximal path cover for a DAG [3-7, 9, 13, 17] is studied and the problem is shown to belong to class NC when either in-degree or out-degree is at most 2. From this result it can be shown that the maximal bipartite matching problem is also in class NC when the degree of one of the node sets is at most 2.
Given a set of n entities to be classified, and a matric of dissimilarities between pairs of them. This paper considers the problem called MINIMUM SUM OF DIAMETERS CLUSTERING PROBLEM, where a partition of the set of e...
详细信息
ISBN:
(纸本)9781467378253
Given a set of n entities to be classified, and a matric of dissimilarities between pairs of them. This paper considers the problem called MINIMUM SUM OF DIAMETERS CLUSTERING PROBLEM, where a partition of the set of entities into k clusters such that the sum of the diameters of these clusters is minimized. Brucker showed that the complexity of the problem is NP-hard, when k >= 3 [1]. For the case of k = 2, Hansen and Jaumard gave an O(n(3) log n) algorithm [2], which Ramnath later improved the running time to O(n(3)) [3]. This paper discusses the parallel complexity of the MINIMUM SUM OF DIAMETERS CLUSTERING PROBLEM. For the case of k = 2, we show that the problem in parallel in fact belongs in class NC.(1) In particular, we show that the parallel complexity of the problem is O(log n) parallel time and n(7) processors on the COMMON CRCW PRAM model. Additionally, we propose the parallel algorithmic technique which can be applied to improve the processor bound by a factor of n. As a result, we show that the problem can be quickly solved in O(log n) parallel time using n(6) processors on the COMMON CRCW PRAM model. In addition, regarding the issue of high processor complexity, we also propose a more practical NC algorithm which can be implemented in O(log(3) n) parallel time using n(3.376) processors on the EREW PRAM model.
It is shown by means of a constructive procedure, that the real and distinct zeros of a polynomialf(x) of degreencan be computed in0(nlog2n) parallel steps using at most0(n) processors.
It is shown by means of a constructive procedure, that the real and distinct zeros of a polynomialf(x) of degreencan be computed in0(nlog2n) parallel steps using at most0(n) processors.
In this paper, we give a novel insight into studying the low level vision. We attack low level problems by parallel information-based complexity techniques. Here we only study the visual surface reconstruction. We obt...
详细信息
In this paper, we give a novel insight into studying the low level vision. We attack low level problems by parallel information-based complexity techniques. Here we only study the visual surface reconstruction. We obtain tight bounds on the complexity, considered as a function of two variables simultaneously: the number of processors, the required precision. This result seems to be new even in serial case. Our results will provide a benchmark for the intrinsic difficulty of visual surface reconstruction. With this, one can compare its computational complexity with the cost any algorithm that solves the problem to tell how well the given algorithm measures up. To the best of our knowledge, it is the first attempt to introduce parallel information-based complexity techniques into studying low level vision.
This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. This analysis shows that the well-known asmptot...
详细信息
This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. This analysis shows that the well-known asmptotically optimal results are insufficient because we show that the overhead is in O(n3). The optimal parallel time with O(n) processors is only O(n2). The new scheduling algorithm that we have proposed in this paper reduces the overhead to only O(n2) with the same parallel time.
The parallel complexity of the simultaneous approximation to all the zeros of a polynomial is investigated. By modifying and analyzing an algorithm given by Householder, it is possible to obtain a priori bounds to the...
详细信息
The parallel complexity of the simultaneous approximation to all the zeros of a polynomial is investigated. By modifying and analyzing an algorithm given by Householder, it is possible to obtain a priori bounds to the number of iterations sufficient to yield a given accuracy, and to the number of digits required in the finite arithmetic. More classes of polynomials, for which the simultaneous approximation to all the zeros can be carried out in polylogarithmic time, are found. Some cases of polynomials, customarily considered hard, are easily solved. The root-finding problem for a polynomial of degree n, having zeros z(i), i = 1, ..., n is NC-reduced to finding a polynomial a(z) such that \a(z(i) + 1) /a(z(i))\ less-than-or-equal-to 1 - 1 /n(c), where c is a constant.
作者：
Ubeda, STSI-CNRS URA n°842
Universite Jean-Monnet 23 Rue Docteur Michelon 42023 Saint-Etienne France
We propose a parallel thinning algorithm for binary pictures. Given an N x N binary image including an object, our algorithm computes in O(N-2) the skeleton of the object, using a pyramidal decomposition of the pictur...
详细信息
We propose a parallel thinning algorithm for binary pictures. Given an N x N binary image including an object, our algorithm computes in O(N-2) the skeleton of the object, using a pyramidal decomposition of the picture. The behavior of this algorithm is studied considering a family of digitalization of the same object at a different level of resolution. With the Exclusive Read Exclusive Write (EREW) parallel Random Access Machine (PRAM), our algorithm runs in O(log N) time using O(N-2/log N) processors and it is work-optimal. The same result is obtained with high-connectivity distributed memory SIMD machines having strong hypercube and pyramid. We describe the basic operator, the pyramidal algorithm and some experimental results on the SIMD MasPar parallel machine.
暂无评论