Dynamic and multi-functional labeling schemes

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

doi:10.1007/978-3-319-13075-0_12

Dynamic and multi-functional labeling schemes

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

Department of Computer Science

1 Citation (Scopus)

Abstract

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.

Original language	English
Title of host publication	Algorithms and Computation : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings
Editors	Hee-Kap Ahn, Chan-Su Shin
Number of pages	13
Publisher	Springer
Publication date	2014
Pages	141-153
Chapter	12
ISBN (Print)	978-3-319-13074-3
ISBN (Electronic)	978-3-319-13075-0
DOIs	https://doi.org/10.1007/978-3-319-13075-0_12
Publication status	Published - 2014
Event	International Symposium, ISAAC 2014 - Jeonju, Korea, Republic of Duration: 15 Dec 2014 → 17 Dec 2014 Conference number: 25

Conference

Conference	International Symposium, ISAAC 2014
Number	25
Country/Territory	Korea, Republic of
City	Jeonju
Period	15/12/2014 → 17/12/2014

Series	Lecture notes in computer science
ISSN	0302-9743

Access to Document

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

Cite this

Dynamic and multi-functional labeling schemes. / Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs; Rotbart, Noy Galil.

Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings. ed. / Hee-Kap Ahn; Chan-Su Shin. Springer, 2014. p. 141-153 (Lecture notes in computer science).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Dahlgaard, S, Knudsen, MBT & Rotbart, NG 2014, Dynamic and multi-functional labeling schemes. in H-K Ahn & C-S Shin (eds), Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings. Springer, Lecture notes in computer science, pp. 141-153, International Symposium, ISAAC 2014, Jeonju, Korea, Republic of, 15/12/2014. https://doi.org/10.1007/978-3-319-13075-0_12

@inproceedings{619ab8d1e4d245abbeb16b783cc32e44,

title = "Dynamic and multi-functional labeling schemes",

abstract = "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{\textquoteright}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{\textquoteright}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{\textquoteright}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.",

author = "S{\o}ren Dahlgaard and Knudsen, {Mathias B{\ae}k Tejs} and Rotbart, {Noy Galil}",

year = "2014",

doi = "10.1007/978-3-319-13075-0_12",

language = "English",

isbn = "978-3-319-13074-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "141--153",

editor = "Hee-Kap Ahn and Chan-Su Shin",

booktitle = "Algorithms and Computation",

note = "International Symposium, ISAAC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

}

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 -

Dynamic and multi-functional labeling schemes

Abstract

Conference

Access to Document

Fingerprint

Cite this