Parallel N-free order recognition

Abstract : Parallel algorithms for recognizing and representing N-free orders are proposed for different models of parallel random access machine (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 model and in constant time using n^2 processors in the CRCW PRAM model. Algorithms for distributed-memory machines are also proposed.
Liste complète des métadonnées

https://hal.inria.fr/inria-00471609
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:33
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 20:38:57

Fichiers

tcs97.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Laurent Viennot. Parallel N-free order recognition. Theoretical Computer Science, Elsevier, 1997, 175, pp.393-406. 〈10.1016/S0304-3975(96)00210-1〉. 〈inria-00471609〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

65