Dynamic and multi-functional labeling schemes

TY - GEN

T1 - Dynamic and multi-functional labeling schemes

AU - Dahlgaard, Søren

AU - Knudsen, Mathias Bæk Tejs

AU - Rotbart, Noy Galil

N1 - Conference code: 25

PY - 2014

Y1 - 2014

N2 - We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of log n + O(log log n) labeling schemes supporting each of these functions was proven, with the most recent being ancestry [Fraigniaud andKorman, STOC’10]. Severalmulti-functional labeling schemes also enjoy lower or upper bounds of log n+Ω(log log n) or logn+ O(log log n) respectively. Notably an upper bound of log n+2log log n for adjacency+siblings and a lower bound of log n + log log n for each of the functions siblings, ancestry, and connectivity [Alstrup et al., SODA’03]. We improve the constants hidden in the O-notation, where our main technical contribution is a log n+2log log n lower bound for connectivity +ancestry and connectivity+siblings. In the context of dynamic labeling schemes it is known that ancestry requires Ω(n) bits [Cohen, et al. PODS’02]. In contrast, we show upper and lower bounds on the label size for adjacency, siblings, and connectivity of 2 log n bits, and 3 log n to support all three functions. We also show that there exist no efficient dynamic adjacency labeling schemes for planar, bounded treewidth, bounded arboricity and bounded degree graphs.

AB - We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of log n + O(log log n) labeling schemes supporting each of these functions was proven, with the most recent being ancestry [Fraigniaud andKorman, STOC’10]. Severalmulti-functional labeling schemes also enjoy lower or upper bounds of log n+Ω(log log n) or logn+ O(log log n) respectively. Notably an upper bound of log n+2log log n for adjacency+siblings and a lower bound of log n + log log n for each of the functions siblings, ancestry, and connectivity [Alstrup et al., SODA’03]. We improve the constants hidden in the O-notation, where our main technical contribution is a log n+2log log n lower bound for connectivity +ancestry and connectivity+siblings. In the context of dynamic labeling schemes it is known that ancestry requires Ω(n) bits [Cohen, et al. PODS’02]. In contrast, we show upper and lower bounds on the label size for adjacency, siblings, and connectivity of 2 log n bits, and 3 log n to support all three functions. We also show that there exist no efficient dynamic adjacency labeling schemes for planar, bounded treewidth, bounded arboricity and bounded degree graphs.

U2 - 10.1007/978-3-319-13075-0_12

DO - 10.1007/978-3-319-13075-0_12

M3 - Article in proceedings

SN - 978-3-319-13074-3

T3 - Lecture notes in computer science

SP - 141

EP - 153

BT - Algorithms and Computation

A2 - Ahn, Hee-Kap

A2 - Shin, Chan-Su

PB - Springer

T2 - International Symposium, ISAAC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -