Adjacency Labeling Schemes and Induced-Universal Graphs
Adjacency Labeling Schemes and Induced-Universal Graphs
复制标题
邻接标记方案和归纳通用图
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
Stephen Alstrup;Haim Kaplan;M. Thorup;Uri Zwick
我们描述了一种将标签分配给最多n个顶点的任何无向图的顶点的方法，每个顶点由N/2+O（1）位组成，因此给定两个顶点的标签，没有其他有关图形的信息，可以决定图表中的顶点是否相邻。这是最佳的，达到添加剂常数，并且构成了月球N/2+O（log n）的近50年中的第一个改进。结果，我们获得了仅包含O（2n/2）顶点的N vertex图的诱导的宇宙图，该图是最佳的，最佳至乘法常数，解决了从1968年开始的开放式问题。我们获得了类似的紧密结果。定向图，锦标赛和两部分图。
We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.