2014/07/18 by Søren Dahlgaard, Dahlgaard, Søren, Mathias Bæk Tejs Knudsen +3
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1407.5011
12 pages, 1 figure. To appear at ICALP'15
openalex publication_date 2014/07/18 · arxiv created 2015/04/26 · arxiv updated 2015/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.