Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Laurent Viennot Connect in order to contact the contributor
Submitted on : Thursday, April 8, 2010 - 4:13:14 PM
Last modification on : Saturday, November 20, 2021 - 3:50:09 AM
Long-term archiving on: : Friday, July 9, 2010 - 9:17:29 PM


Files produced by the author(s)



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⟩



Record views


Files downloads