Efficient Parallel Shuffle Recognition

M. Nivat, G.D.S. Ramkumar, C. Pandu Rangan, A. Saoudi, R. Sundaram

IBP-Litp 1994/55: Rapport de Recherche Litp / Litp research reports
16 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Efficient Parallel Shuffle Recognition

Résumé : Cet article décrit un algorithme parallèle pour décider si un mot X appartient au shuffe de deux mots Y et Z . Cet algorithme prend un temps en 0 (log2 n ) avec 0 ( n 2 / log2 n ) sur une machine EREM-PRAM.

Abstract : This paper presents a parallel algorithm for verifing if a string X is formed by the shuffle of two strings Y and Z . The algorithm runs in O ( log2 n ) time with 0 (n 2 / log 2 n ) processors on the EREW -PRAM model.

Publications internes Litp 1994 / Litp research reports 1994