Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal top dag compression
| Content Provider | arXiv |
|---|---|
| Author | Lohrey, Markus Reh, Carl Philipp Sieber, Kurt |
| Date of Submission | 2017-12-15 |
| Abstract | It is shown that for a given ordered node-labelled tree of size $n$ and with $s$ many different node labels, one can construct in linear time a top dag of height $O(\log n)$ and size $O(n / \log_\sigma n) \cap O(d \cdot \log n)$, where $\sigma = \max\{ 2, s\}$ and $d$ is the size of the minimal dag. The size bound $O(n / \log_\sigma n)$ is optimal and improves on previous bounds. |
| Related Links | https://arxiv.org/pdf/1712.05822.pdf |
| arXiv | 1712.05822 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Data Structures and Algorithms Computer Science Data structures Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
