검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Polynomially Fast Parallel Algorithms for Some P-Complete Problems 일부를 위한 다항적으로 빠른 병렬 알고리즘 P-완전한 문제

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

  • 조회수

    0

  • 이것을 인용

요약 :

P-완전한 문제에는 다항식 수의 프로세서를 사용하여 다대수 시간에 실행되는 병렬 알고리즘이 없는 것 같습니다. ㅏ P-수업에 완전한 문제가 있습니다. EP (효율적이고 다항적으로 빠름) 문제를 해결하기 위한 비용 최적 알고리즘이 존재하는 경우에만 T(n) = O(t(n)ε) (ε < 1) 사용 P(n) 프로세서 T(n) P(n) = O(t(n)), 어디 t(n)는 문제를 해결하는 가장 빠른 순차 알고리즘의 시간 복잡도입니다. 우리 연구의 목표는 다음을 찾는 것입니다. EP 일부를 위한 병렬 알고리즘 P-완전한 문제. 본 논문에서는 먼저 볼록 레이어 문제를 고려합니다. 우리는 세트의 볼록 레이어를 계산하는 알고리즘을 제공합니다. S of n 비행기의 점. 허락하다 k 볼록한 층의 수 S. 1일 때 k nε/2 (0 ε < 1) 우리의 알고리즘은 다음과 같이 실행됩니다. O((n 기록 n)/p) 사용 시간 p 프로세서, 여기서 1 p n1-ε/2, 비용 최적입니다. 다음으로 세트의 엔벨로프 레이어 문제를 고려합니다. S of n 평면의 선분. 허락하다 k 엔벨로프 레이어의 수 S. 1일 때 k nε/2 (0 ε < 1), 우리는 엔벨로프 레이어를 계산하기 위한 알고리즘을 제안합니다. S in O((n α(n) 로그3 n)/p) 사용 시간 p 프로세서, 여기서 1 p n1-ε/2및 α(n)는 매우 느리게 증가하는 Ackermann 함수의 역함수입니다. 이 논문에서 사용하는 계산 모델은 크루-PRAM. 볼록 레이어 문제에 대한 첫 번째 알고리즘은 다음에 속합니다. EP, 봉투 레이어 문제에 대한 두 번째 것은 클래스에 속합니다 EP 로그의 작은 요소인 경우 n 무시됩니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1244-1255
발행일
2001/05/01
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드