Name
Abstract | ||
|---|---|---|
We consider the problem of maintaining a string of n brackets '('or')' under the operation reverse(i) that changes the ith bracket from '('to')' or vice versa, and returns 'yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(logn/log log n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Ω(log n/log log n) per operation in the cell probe model. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ic.2004.04.006 | Inf. Comput. |
Keywords | Field | DocType |
preprocessing complexity,log log n,cell probe model,dynamic nested bracket,resulting string,time o,operation reverse,n bracket,log n,data structure,linear space | Log-log plot,Discrete mathematics,Data structure,Binary logarithm,Combinatorics,Linear space,Bracket,Time complexity,Versa,Mathematics,Cell-probe model | Journal |
Volume | Issue | ISSN |
193 | 2 | Information and Computation |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen Alstrup | 1 | 657 | 42.60 |
| Thore Husfeldt | 2 | 733 | 40.87 |
| Theis Rauhe | 3 | 661 | 35.11 |