An Adjacency Labeling Scheme based on a Decomposition of Trees into Caterpillars
Abstract
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.
Recommended Citation
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
Department(s)
Computer Science
Keywords and Phrases
Clique-Widths; Hereditary Classes; Implicit Representation
International Standard Book Number (ISBN)
978-303106677-1
International Standard Serial Number (ISSN)
1611-3349; 0302-9743
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2022 Springer, All rights reserved.
Publication Date
01 Jan 2022
Comments
This work was supported by the Defense Technical Information Center, Grant FA8075-14-D-0002/0007.