An Adjacency Labeling Scheme based on a Decomposition of Trees into Caterpillars
In this paper we look at the problem of adjacency labeling of graphs. Given a family of undirected graphs the problem is to determine an encoding-decoding scheme for each member of the family such that we can decode the adjacency information of any pair of vertices only from their encoded labels. Further, we want the length of each label to be short (logarithmic in n, the number of vertices) and the encoding-decoding scheme to be computationally efficient. We propose a simple tree-decomposition based encoding scheme and use it give an adjacency labeling of size O(klog klog n) -bits. Here k is the clique-width of the graph family. We also extend the result to a certain family of k-probe graphs.
A. Banerjee, "An Adjacency Labeling Scheme based on a Decomposition of Trees into Caterpillars," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13270 LNCS, pp. 114 - 127, Springer Verlag, Jan 2022.
The definitive version is available at https://doi.org/10.1007/978-3-031-06678-8_9
Keywords and Phrases
Clique-Widths; Hereditary Classes; Implicit Representation
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 2022 Springer, All rights reserved.
01 Jan 2022
This work was supported by the Defense Technical Information Center, Grant FA8075-14-D-0002/0007.