Technical Report 477-1995
- Title
- A compact data structure and parallel algorithms for permutation graphs
- Authors
- Jens Gustedt, Michel Morvan, and Laurent Viennot
- Publication
- Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG
- Source
- Download as [ps.gz]
- Classification
-
not available
- Keywords
-
not available
-
Starting from a permutation of {0,ldots,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.