Work-time-optimal parallel algorithms for string problems
Artur Czumaj, Zvi Galil, Leszek Antoni Gąsieniec, Kunsoo Park, Wojciech Plandowski · 1995
A parallel algorithm is work-optimal if it uses the srrlallest possible work; a work-optimal algorithm is worktirne-optimal if it also uses the smallest possible time.We design worl{-time-optirnal algorithm for a number of string processing problems on the EREW-PRAM and the hypercuhe, They include string matching and two dimensional pattern matching.No such algorithms have been known before for any of these probl~ms.