2014/04/19 by Søren Dahlgaard, Dahlgaard, Søren, Mathias Bæk Tejs Knudsen +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.4982
17 pages, 5 figures
arxiv created 2014/04/19 · arxiv updated 2014/04/22
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) labeling schemes supporting each of these functions was proven, with the most recent being ancestry [Fraigniaud and Korman, STOC '10]. Several multi-functional labeling schemes also enjoy lower or upper bounds of log n + Ω(log log n) or log n + O(log log n) respectively. Notably an upper bound of log n + 5log 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. In particular we show a log n + 2log log n lower bound for connectivity+ancestry and connectivity+siblings, as well as an upper bound of log n + 3log log n + O(log log log n) for connectivity+adjacency+siblings by altering existing methods. 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 2log n bits, and 3 log n to support all three functions. There exist efficient adjacency labeling schemes for planar, bounded treewidth, bounded arboricity and interval graphs. In a dynamic setting, we show a lower bound of Ω(n) for each of those families.