Polynomially Fast Parallel Algorithms for Some <I>P</I>-Complete Problems

Carla Denise CASTANHO; Wei CHEN; Koichi WADA; Akihiro FUJIWARA

Polynomially Fast Parallel Algorithms for Some P-Complete Problems

Carla Denise CASTANHO, Wei CHEN, Koichi WADA, Akihiro FUJIWARA

Full Text Views

0

Cite this

Summary :

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)^ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k n^ε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n^1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k n^ε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O^{((n α(n) log³ n)/p)} time using p processors, where 1 p n^1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1244-1255

Publication Date: 2001/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Carla Denise CASTANHO, Wei CHEN, Koichi WADA, Akihiro FUJIWARA, "Polynomially Fast Parallel Algorithms for Some P-Complete Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E84-A, no. 5, pp. 1244-1255, May 2001, doi: .
Abstract: P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)^ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k n^ε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n^1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k n^ε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O^{((n α(n) log³ n)/p)} time using p processors, where 1 p n^1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1244/_p

Copy

@ARTICLE{e84-a_5_1244,
author={Carla Denise CASTANHO, Wei CHEN, Koichi WADA, Akihiro FUJIWARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Polynomially Fast Parallel Algorithms for Some P-Complete Problems},
year={2001},
volume={E84-A},
number={5},
pages={1244-1255},
abstract={P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)^ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k n^ε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n^1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k n^ε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O^{((n α(n) log³ n)/p)} time using p processors, where 1 p n^1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Polynomially Fast Parallel Algorithms for Some P-Complete Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1244
EP - 1255
AU - Carla Denise CASTANHO
AU - Wei CHEN
AU - Koichi WADA
AU - Akihiro FUJIWARA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)^ε) (ε < 1) using P(n) processors such that T(n) P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1 k n^ε/2 (0 ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1 p n^1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1 k n^ε/2 (0 ε < 1), we propose an algorithm for computing the envelope layers of S in O^{((n α(n) log³ n)/p)} time using p processors, where 1 p n^1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.
ER -