Since 2014
An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
|
|
| Creator |
Apostolico, Alberto
Breslauer, Dany |
|
| Description |
An optimal O(log log n) time concurrent-read concurrent-write parallelalgorithm for detecting all squares in a string is presented. A tightlower bound shows that over general alphabets this is the fastest possibleoptimal algorithm. When p processors are available the bounds becomeTheta(n log n / p + log log 2p). The algorithm uses an optimal parallelstring-matching algorithm together with periodicity properties to locatethe squares within the input string.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1995-01-11
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19514
10.7146/brics.v2i11.19514 |
|
| Source |
BRICS Report Series; No 11 (1995): RS-11 An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
BRICS Report Series; No 11 (1995): RS-11 An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19514/17135
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|