,
Parallel algorithms for separable permutations
Discrete Applied Mathematics, 146 (3): 343 - 364 (2005)
DOI: http://dx.doi.org/10.1016/j.dam.2004.10.004
Аннотация
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 ( log n ) 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 ( log n ) time with O ( n 2 ) cost or alternatively in O ( d log n ) 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 ( d log n ) time with O ( kn 4 ) cost (the same as that of the serial algorithm). We can also find the number of matches of P in T in O ( d log n ) time with O ( kn 6 ) 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 ( kn 3 ) to O ( n 3 log k ) and of the counting version from O ( kn 4 ) to O ( n 4 log k ) .
