A simple and optimal ancestry labeling scheme for trees

DOI10.1007/978-3-662-47666-6_45zbMATH Open1440.68048arXiv1407.5011OpenAlexW2247301512MaRDI QIDQ3449505FDOQ3449505

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)

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.

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

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)

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

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)