Name
Abstract | ||
|---|---|---|
We consider the succinct representation of ordinal and cardinal trees on the RAM with logarithmic word size. Given a tree T , our representations support the following operations in O (1) time: (i) $\mbox{{\tt BP-substring}}(i,b)$, which reports the substring of length b bits (b is at most the wordsize) beginning at position i of the balanced parenthesis representation of T , (ii) $\mbox{{\tt DFUDS-substring}}(i,b)$, which does the same for the depth first unary degree sequence representation, and (iii) a similar operation for tree-partition based representations of T . We give: an asymptotically space-optimal 2n + o (n ) bit representation of n -node ordinal trees that supports all the above operations with b = *** (logn ), answering an open question from [He et al., ICALP'07]. an asymptotically space-optimal C (n ,k ) + o (n )-bit representation of k -ary cardinal trees, that supports (with $b = \Theta(\sqrt{\log n})$) the operations (ii) and (iii) above, on the ordinal tree obtained by removing labels from the cardinal tree, as well as the usual label-based operations. As a result, we obtain a fully-functional cardinal tree representation with the above space complexity. This answers an open question from [Raman et al, SODA'02]. Our new representations are able to simultaneously emulate the BP, DFUDS and partitioned representations using a single instance of the data structure, and thus aim towards universality . They not only support the union of all the ordinal tree operations supported by these representations, but will also automatically inherit any new operations supported by these representations in the future. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02927-1_38 | ICALP |
Keywords | Field | DocType |
balanced parenthesis representation,succinct representation,open question,unary degree sequence representation,new representation,partitioned representation,fully-functional cardinal tree representation,cardinal tree,universal succinct representations,asymptotically space-optimal,bit representation,space complexity,data structure,degree sequence | Discrete mathematics,Binary logarithm,Data structure,Combinatorics,Substring,Unary operation,Ordinal number,Depth-first search,Binary tree,Degree (graph theory),Mathematics | Conference |
Volume | ISSN | Citations |
5555 | 0302-9743 | 14 |
PageRank | References | Authors |
0.62 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Farzan | 1 | 136 | 11.07 |
| Rajeev Raman | 2 | 1550 | 110.81 |
| S. Srinivasa Rao | 3 | 786 | 49.95 |