TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1995

COGA 5-Wheel

Page Content

to Navigation

Preprints 1995

A compact data structure and parallel algorithms for permutation graphs
Citation key Report-477-1995
Author Jens Gustedt and Michel Morvan and Laurent Viennot
Year 1995
Number 477
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Starting from a permutation of $\0,łdots,n-1\$ we compute in parallel with a workload of $O(n łog n)$ a compact data structure of size $O(n łog 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 łog n)$ where $m$ is the number of edges of the permutation graph. They run in time $O(łog^2 n)$ on a CREW PRAM.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe