Dynamic and multi-functional labeling schemes

DOI10.1007/978-3-319-13075-0_12MaRDI QIDQ2942623zbMATH OpenOpenAlexFDO

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

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4982

zbMATH Keywords

dynamic labeling schemes

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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 $logn+O(loglog)$ 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 $logn+Omega(loglogn)$ or $logn+O(loglogn)$ respectively. Notably an upper bound of $logn+5loglogn$ for adjacency+siblings and a lower bound of $logn+loglogn$ 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 $logn+2loglogn$ lower bound for connectivity+ancestry and connectivity+siblings, as well as an upper bound of $logn+3loglogn+O(logloglogn)$ for connectivity+adjacency+siblings by altering existing methods. In the context of dynamic labeling schemes it is known that ancestry requires $Omega(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 $2logn$ bits, and $3logn$ 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 $Omega(n)$ for each of those families.

Recommendations

• General compact labeling schemes for dynamic trees
• Distributed Computing
• Labeling schemes for dynamic tree networks
• Labeling Schemes with Queries
• scientific article; zbMATH DE number 2079400

Cited in

(7)

• Algorithms and Data Structures
• Rowmotion and increasing labeling promotion
• Dynamic labeled 2-structures
• Fully Dynamic 2-Hop Cover Labeling
• Incremental labeling in closed-2PM model
• Labeling schemes for bounded degree graphs
• Labeling Schemes with Queries

This page was built for publication: Dynamic and multi-functional labeling schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942623)