Parallel algorithms for separable permutations

In this paper, it is shown that on the CREW model we can test whether a given permutation of 1,…,n is separable in O(logn) time with n processors. If d is the depth of the optimal (minimum) depth separating tree of a separable permutation, then a separating tree of depth Θ(d) can be constructed on the CREW model in O(logn) time with O(n2) cost or alternatively in O(dlogn) time with O(nd) cost. We can test whether the given separable permutation P of 1,…,k has a match in a permutation T of 1,…,n (n⩾k) in O(dlogn) time with O(kn4) cost (the same as that of the serial algorithm). We can also find the number of matches of P in T in O(dlogn) time with O(kn6) cost (the same as that of the serial algorithm). Both algorithms are for the CREW model. We also discuss how the space complexity of the existing serial algorithms for the decision problem can be reduced from O(kn3) to O(n3logk) and of the counting version from O(kn4) to O(n4logk).