La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Algorithmes parallèles polynomialement rapides pour certains P-Problèmes complets

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

  • Vues en texte intégral

    0

  • Citer

Résumé:

P-les problèmes complets ne semblent pas avoir d'algorithme parallèle qui s'exécute en temps polylogarithmique en utilisant un nombre polynomial de processeurs. UN P-le problème complet est dans la classe EP (Efficace et polynomialement rapide) si et seulement s'il existe un algorithme optimal en termes de coût pour le résoudre en T(n) = O(t(n)ε) (ε < 1) en utilisant P(n) processeurs tels que T(n) P(n) = O(t(n)), où t(n) est la complexité temporelle de l'algorithme séquentiel le plus rapide qui résout le problème. Le but de notre recherche est de trouver EP algorithmes parallèles pour certains P-problèmes complets. Dans cet article, nous considérons d’abord le problème des couches convexes. Nous donnons un algorithme pour calculer les couches convexes d'un ensemble S of n points dans le plan. Laisser k être le nombre de couches convexes de S. Quand 1 k nε/2 (0 ε < 1) notre algorithme s'exécute dans O((n enregistrer n)/p) temps d'utilisation p processeurs, où 1 p n1-ε/2, et son coût est optimal. Ensuite, nous considérons le problème des couches d’enveloppe d’un ensemble S of n segments de droite dans le plan. Laisser k être le nombre de couches d'enveloppe de S. Quand 1 k nε/2 (0 ε < 1), nous proposons un algorithme de calcul des couches d'enveloppe de S in O((n α(n) log3 n)/p) temps d'utilisation p processeurs, où 1 p n1-ε/2, et α(n) est l'inverse fonctionnel de la fonction d'Ackermann qui croît extrêmement lentement. Le modèle informatique que nous utilisons dans cet article est le ÉQUIPAGE-PRAM. Notre premier algorithme, pour le problème des couches convexes, appartient à EP, et le second, pour le problème des couches d'enveloppe, appartient à la classe EP si un petit facteur de log n est ignoré.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1244-1255
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières