A Compact Data Structure and Parallel Algorithms for Permutation Graphs

J. Gustedt, M. Morvan, L. Viennot

IBP-Litp 1995/38: Rapport de Recherche Litp / Litp research reports
11 pages - Juillet/July 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: A Compact Data Structure and Parallel Algorithms for Permutation Graphs

Résumé : Partant d'une permutation de {0,...,n-1}, on calcule en parallèle avec un travail en O(n log n) une structure de données de taille O(n log n). Cette structure de données permet d'obtenir efficacement le graphe associé à la permutation, la fermeture et la réduction transitive de l'ordre de dimension 2 correspondant.
Les algorithmes parallèles obtenus ont un travail en O(m + n log n) où m représente le nombre d'arêtes du graphe. Tous les algorithmes présentés s'exécutent en temps O(log2 n) sur une CREW PRAM.

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(m + n log n) where m is the number of edges of the permutation graph. They run in time O(log2 n) on a CREW PRAM.

Publications internes Litp 1995 / Litp research reports 1995