EFFICIENT PARALLEL SHUFFLE RECOGNITION
Maurice Nivat, G. D. Ramkumar, Chandrasekharan Pandu Rangan, A. Saoudi, R. Sundaram · Parallel Processing Letters · 1994
This paper presents a parallel algorithm for verifying that a string X is formed by the shuffle of two strings Y and Z. The algorithm runs in O(log2n) time with O(n2/log2 n) processors on the EREW-PRAM model.