Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Simple and Optimal Ancestry Labeling Scheme for Trees
verfasst von : Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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+O(1)$$
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.