A compact data structure and parallel algorithms for permutation graphs

Abstract : Starting from a permutation of {0,...,n-1} we compute in parallel with a workload of O(n log n) a compact data structure of size O(n log n). This data structure allows to obtain the associated permutation graph and the transitive closure and reduction of the associated order of dimension 2 efficiently. The parallel algorithms obtained have a workload of O(n + m log n) where m is the number of edges of the permutation graph. They run in time O(log^2 n) on a CREW PRAM
Type de document :
Communication dans un congrès
M. Nagl. 21st Workshop on Graph-Theoretic Concepts in computer Science (WG), 1995, Aachen, Germany. Springer Berlin / Heidelberg, 1017, pp.372-380, 1995, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/f161001272763092/〉. 〈10.1007/3-540-60618-1〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00471607
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:14
Dernière modification le : jeudi 11 janvier 2018 - 01:52:00
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:17:29

Fichiers

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

Identifiants

Collections

Citation

Jens Gustedt, Michel Morvan, Laurent Viennot. A compact data structure and parallel algorithms for permutation graphs. M. Nagl. 21st Workshop on Graph-Theoretic Concepts in computer Science (WG), 1995, Aachen, Germany. Springer Berlin / Heidelberg, 1017, pp.372-380, 1995, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/f161001272763092/〉. 〈10.1007/3-540-60618-1〉. 〈inria-00471607〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

58