论文标题
基于树分解的邻接标签方案
An adjacency labeling scheme based on a tree-decomposition
论文作者
论文摘要
在本文中，我们查看图形标记的问题。给定一个无向图的家族，问题是为每个家庭成员确定一个编码编码方案，以便我们只能从其编码标签中解码任何一对顶点的邻接信息。此外，我们希望每个标签的长度很短（$ n $的对数，顶点数）和编码编码方案的计算有效。我们提出了一个简单的基于树分解的编码方案，并使用它给出了大小$ o（k \ log k \ log n）$ - 位的相邻标记。这里$ k $是图形家族的集团宽度。我们还将结果扩展到某个$ k $ - 探针图的家族。
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 proposed a simple tree-decomposition based encoding scheme and used it give an adjacency labeling of size $O(k \log k \log 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.
