A simple and optimal ancestry labeling scheme for trees

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • Søren Dahlgaard
  • Mathias Bæk Tejs Knudsen
  • Noy Galil Rotbart

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 languageEnglish
Title of host publicationAutomata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II
EditorsMagnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
Number of pages11
PublisherSpringer
Publication date2015
Pages564-574
ISBN (Print)978-3-662-47665-9
ISBN (Electronic)978-3-662-47666-6
DOIs
Publication statusPublished - 2015
EventInternational Colloquium on Automata, Languages and Programming 2015 - Kyoto, Japan
Duration: 6 Jul 201510 Jul 2015
Conference number: 42

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming 2015
Nummer42
LandJapan
ByKyoto
Periode06/07/201510/07/2015
SponsorERATO 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
SeriesLecture notes in computer science
Volume9135
ISSN0302-9743

ID: 159746595