Near-optimal labeling schemes for nearest common ancestors

TY - GEN

T1 - Near-optimal labeling schemes for nearest common ancestors

AU - Alstrup, Stephen

AU - Halvorsen, Esben Bistrup

AU - Larsen, Kasper Green

N1 - Conference code: 25

PY - 2014

Y1 - 2014

N2 - We consider NCA labeling schemes: given a rooted tree T, label the nodes of T with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the label of their nearest common ancestor. For trees with n nodes we present upper and lower bounds establishing that labels of size (2 ± ε)logn, ε < 1 are both sufficient and necessary.Alstrup, Bille, and Rauhe (SIDMA'05) showed that ancestor and NCA labeling schemes have labels of size logn + Ω(loglogn ). Our lower bound increases this to logn + Ω(logn) for NCA labeling schemes. Since Fraigniaud and Korman (STOC'10) established that labels in ancestor labeling schemes have size logn+Θ(log logn), our new lower bound separates ancestor and NCA labeling schemes. Our upper bound improves the 10 log n upper bound by Alstrup, Gavoille, Kaplan and Rauhe (TOCS'04), and our theoretical result even outperforms some recent experimental studies by Fischer (ESA'09) where variants of the same NCA labeling scheme are shown to all have labels of size approximately 8 log n.

AB - We consider NCA labeling schemes: given a rooted tree T, label the nodes of T with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the label of their nearest common ancestor. For trees with n nodes we present upper and lower bounds establishing that labels of size (2 ± ε)logn, ε < 1 are both sufficient and necessary.Alstrup, Bille, and Rauhe (SIDMA'05) showed that ancestor and NCA labeling schemes have labels of size logn + Ω(loglogn ). Our lower bound increases this to logn + Ω(logn) for NCA labeling schemes. Since Fraigniaud and Korman (STOC'10) established that labels in ancestor labeling schemes have size logn+Θ(log logn), our new lower bound separates ancestor and NCA labeling schemes. Our upper bound improves the 10 log n upper bound by Alstrup, Gavoille, Kaplan and Rauhe (TOCS'04), and our theoretical result even outperforms some recent experimental studies by Fischer (ESA'09) where variants of the same NCA labeling scheme are shown to all have labels of size approximately 8 log n.

U2 - 10.1137/1.9781611973402.72

DO - 10.1137/1.9781611973402.72

M3 - Article in proceedings

SN - 978-1-61197-338-9

SP - 972

EP - 982

BT - Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Chekuri, Chandra

PB - Society for Industrial and Applied Mathematics

T2 - Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 2014 through 7 January 2014

ER -