论文标题
最佳标签方案，可用于邻接性，可比性和可及性
Optimal labelling schemes for adjacency, comparability, and reachability
论文作者
论文摘要
我们为每个遗传阶级构建渐近的最佳邻接标签方案，其中包含$ 2^{ω（n^2）} $ $ n $ vertex图形为$ n \ to \ infty $。该制度包含许多兴趣类别的类别，例如完美的图形或可比性图，为此我们获得了一个邻接标签方案，标签为$ n/4+o（n）$ bits $ littex。这意味着存在针对Digraphs的可及性标签方案，其标签为$ n/4+o（n）$位，每个顶点的$位和可比性标签方案的POSETS方案，其标签为$ n/4+o（n）$ lits $ n元素。所有这些结果都是最好的，直到低阶期限。
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing $2^{Ω(n^2)}$ $n$-vertex graphs as $n\to \infty$. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of $n/4+o(n)$ bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of $n/4+o(n)$ bits per vertex and comparability labelling scheme for posets with labels of $n/4+o(n)$ bits per element. All these results are best possible, up to the lower order term.
