A Simple and Optimal Ancestry Labeling Scheme for Trees
| Autor: | Mathias Bæk Tejs Knudsen, Noy Rotbart, Søren Dahlgaard |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Automata, Languages, and Programming ISBN: 9783662476659 ICALP (2) |
| DOI: | 10.1007/978-3-662-47666-6_45 |
| Popis: | We present a $$\lg n + 2 \lg \lg n+3$$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $$2 \lg n$$ solution. Motivated by applications to XML files, the label size was improved incrementally over the course of more than 20 years by a series of papers. The last, due to Fraigniaud and Korman [STOC 10'], presented an asymptotically optimal $$\lg n + 4 \lg \lg n+O1$$ labeling scheme using non-trivial tree-decomposition techniques. By providing a framework generalizing interval based labeling schemes, we obtain a simple, yet asymptotically optimal solution to the problem. Furthermore, our labeling scheme is attained by a small modification of the original $$2 \lg n$$ solution. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|