Parallel N-free Order Recognition

L. Viennot

IBP-Litp 1995/05: Rapport de Recherche Litp / Litp research reports
16 pages - Février/February 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Parallel N-free Order Recognition

Résumé : Ce papier contient des algorithmes de reconnaissance et de représentation des ordres N-free pour différents modèles parallèles à mémoire partagée (PRAM). Ces algorithmes prennent en entrée un graphe transitivement réduit ayant n sommets et m arrêtes. L'un s'exécute en temps O(log n) avec n+m processeurs dans le modèle EREW PRAM et l'autre en temps constant avec n2 processeurs dans le modèle CRCW PRAM. Des algorithmes pour machines à mémoire distribuée en sont dérivés et présentés.

Abstract : Parallel algorithms for recognizing and representing N-free orders are proposed for different models of parallel random access machines (PRAM). The algorithms accept as input a transitively reduced directed graph with n vertices and m edges. They respectively run in time O(log n) using n+m processors in the EREW PRAM model and in constant time using n2 processors in the CRCW PRAM model. Algorithms for distributed-memory machines are also proposed.

Publications internes Litp 1995 / Litp research reports 1995