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
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00471607
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 4:13:14 PM
Last modification on : Friday, January 4, 2019 - 5:33:25 PM
Long-term archiving on : Friday, July 9, 2010 - 9:17:29 PM

Files

wg95.pdf
Files produced by the author(s)

Identifiers

Citation

Jens Gustedt, Michel Morvan, Laurent Viennot. A compact data structure and parallel algorithms for permutation graphs. 21st Workshop on Graph-Theoretic Concepts in computer Science (WG), 1995, Aachen, Germany. pp.372-380, ⟨10.1007/3-540-60618-1⟩. ⟨inria-00471607⟩

Share

Metrics

Record views

126

Files downloads

129