A simple and optimal ancestry labeling scheme for trees
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II |
Editors | Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann |
Number of pages | 11 |
Publisher | Springer |
Publication date | 2015 |
Pages | 564-574 |
ISBN (Print) | 978-3-662-47665-9 |
ISBN (Electronic) | 978-3-662-47666-6 |
DOIs | |
Publication status | Published - 2015 |
Event | International Colloquium on Automata, Languages and Programming 2015 - Kyoto, Japan Duration: 6 Jul 2015 → 10 Jul 2015 Conference number: 42 |
Conference
Conference | International Colloquium on Automata, Languages and Programming 2015 |
---|---|
Nummer | 42 |
Land | Japan |
By | Kyoto |
Periode | 06/07/2015 → 10/07/2015 |
Sponsor | ERATO Kawarabayashi Large Graph Project, Kyoto University, MEXT Grant-in-Aid for Scientific Research on Innovative Areas, Research Institute for Mathematical Sciences, Tateisi Science and Technology Foundation |
Series | Lecture notes in computer science |
---|---|
Volume | 9135 |
ISSN | 0302-9743 |
ID: 159746595