Journal article
Parallel RAM algorithms for factorizing words
Theoretical Computer Science, Vol.127(1), pp.53-67
1994
Abstract
An O(logn log log n) CRCW PRAM algorithm using O(n/log n) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.
Details
- Title
- Parallel RAM algorithms for factorizing words
- Authors/Creators
- J.W. Daykin (Author/Creator)C.S. Iliopoulos (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.127(1), pp.53-67
- Publisher
- Elsevier BV
- Identifiers
- 991005540403307891
- Copyright
- © 1994 Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
43 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science