An efficient parallel algorithm for building the separating tree
We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log(2) n) time using O(n log(1.5) n) operations on the CREW PRAM and O(log(2) n) time using O(n log n log logo) operations on the COMMON CRCW PRAM. (C) 2010 Elsevier Inc. All rights reserved.
parallel algorithms algorithms separable permutation