Standard
A simple and optimal ancestry labeling scheme for trees. / Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs; Rotbart, Noy Galil.
Automata, languages, and programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II. ed. / Magnús M. Halldórsson; Kazuo Iwama; Naoki Kobayashi; Bettina Speckmann. Springer, 2015. p. 564-574 (Lecture notes in computer science, Vol. 9135).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Dahlgaard, S, Knudsen, MBT & Rotbart, NG 2015,
A simple and optimal ancestry labeling scheme for trees. in MM Halldórsson, K Iwama, N Kobayashi & B Speckmann (eds),
Automata, languages, and programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II. Springer, Lecture notes in computer science, vol. 9135, pp. 564-574, International Colloquium on Automata, Languages and Programming 2015, Kyoto, Japan,
06/07/2015.
https://doi.org/10.1007/978-3-662-47666-6_45APA
Dahlgaard, S., Knudsen, M. B. T., & Rotbart, N. G. (2015).
A simple and optimal ancestry labeling scheme for trees. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.),
Automata, languages, and programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II (pp. 564-574). Springer. Lecture notes in computer science Vol. 9135
https://doi.org/10.1007/978-3-662-47666-6_45Vancouver
Dahlgaard S, Knudsen MBT, Rotbart NG.
A simple and optimal ancestry labeling scheme for trees. In Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, editors, Automata, languages, and programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II. Springer. 2015. p. 564-574. (Lecture notes in computer science, Vol. 9135).
https://doi.org/10.1007/978-3-662-47666-6_45Author
Dahlgaard, Søren ; Knudsen, Mathias Bæk Tejs ; Rotbart, Noy Galil. / A simple and optimal ancestry labeling scheme for trees. Automata, languages, and programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II. editor / Magnús M. Halldórsson ; Kazuo Iwama ; Naoki Kobayashi ; Bettina Speckmann. Springer, 2015. pp. 564-574 (Lecture notes in computer science, Vol. 9135).
Bibtex
@inproceedings{f18b3c636ffb4264b1424c54376d7807,
title = "A simple and optimal ancestry labeling scheme for trees",
abstract = "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{\textquoteright}] 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{\textquoteright}], 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.",
author = "S{\o}ren Dahlgaard and Knudsen, {Mathias B{\ae}k Tejs} and Rotbart, {Noy Galil}",
year = "2015",
doi = "10.1007/978-3-662-47666-6_45",
language = "English",
isbn = "978-3-662-47665-9",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "564--574",
editor = "Halld{\'o}rsson, {Magn{\'u}s M.} and Kazuo Iwama and Naoki Kobayashi and Bettina Speckmann",
booktitle = "Automata, languages, and programming",
address = "Switzerland",
note = "null ; Conference date: 06-07-2015 Through 10-07-2015",
}
RIS
TY - GEN
T1 - A simple and optimal ancestry labeling scheme for trees
AU - Dahlgaard, Søren
AU - Knudsen, Mathias Bæk Tejs
AU - Rotbart, Noy Galil
N1 - Conference code: 42
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-662-47666-6_45
DO - 10.1007/978-3-662-47666-6_45
M3 - Article in proceedings
AN - SCOPUS:84950128629
SN - 978-3-662-47665-9
T3 - Lecture notes in computer science
SP - 564
EP - 574
BT - Automata, languages, and programming
A2 - Halldórsson, Magnús M.
A2 - Iwama, Kazuo
A2 - Kobayashi, Naoki
A2 - Speckmann, Bettina
PB - Springer
Y2 - 6 July 2015 through 10 July 2015
ER -
