Skip to Main content Skip to Navigation
Conference papers

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 : Saturday, March 28, 2020 - 2:10:41 AM
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

247

Files downloads

468