A simple and optimal ancestry labeling scheme for trees

DOI10.1007/978-3-662-47666-6_45MaRDI QIDQ3449505zbMATH OpenOpenAlexFDO

Authors Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.5011

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We present a $lgn+2lglgn+3$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $2lgn$ 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 $lgn+4lglgn+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 $2lgn$ solution.

Recommendations

• Compact ancestry labeling schemes for XML trees
• An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
• An optimal ancestry scheme and small universal posets
• scientific article; zbMATH DE number 2119759
• Compact labeling schemes for ancestor queries. (Extended abstract)

Cites work

• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 2119759 (Why is no real title available?)
• Adjacency labeling schemes and induced-universal graphs
• An optimal ancestry scheme and small universal posets
• Compact Labeling Scheme for Ancestor Queries
• Compact ancestry labeling schemes for XML trees
• Compact labeling schemes for ancestor queries. (Extended abstract)
• Distance labeling in graphs
• Finding Dominators in Directed Graphs
• Implicat Representation of Graphs
• Labeling Dynamic XML Trees
• Labeling Schemes for Flow and Connectivity
• Labeling Schemes for Small Distances in Trees
• Labeling schemes for vertex connectivity
• Near-optimal labeling schemes for nearest common ancestors
• Nearest common ancestors: a survey and a new algorithm for a distributed environment

Cited in

(2)

• Compact ancestry labeling schemes for XML trees
• An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

This page was built for publication: A simple and optimal ancestry labeling scheme for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449505)