Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
复制标题
有界倍维图的禁止设置距离标签
DOI：
10.1145/2818694
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Ittai Abraham;S. Chechik;C. Gavoille;D. Peleg
本文针对倍增维度受α限制的无权图族提出了一种禁止集标记方案。对于该图族中的一个具有n个顶点的图G，以及对于任何期望的精度参数ε > 0，该标记方案在每个顶点存储一个O((1 + ε⁻¹)²α log₂n)位的标记。给定两个端点s和t的标记，以及一组“禁止”顶点和/或边的集合F的标记，我们的方案能够在O((1 + ε⁻¹)²α · |F|² log n)时间内，计算出在图G∖F中s和t之间距离的(1 + ε) - 拉伸近似值。对于有界倍增维度的图，该标记方案可扩展为一种具有(1 + ε)拉伸的禁止集标记路由方案。
This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an n-vertex graph G in this family, and for any desired precision parameter ε > 0, the labeling scheme stores an O(1 + ε− 1)2αlog 2n-bit label at each vertex. Given the labels of two end-vertices s and t, and the labels of a set F of “forbidden” vertices and/or edges, our scheme can compute, in O(1 + ε − 1)2α · |F|2log n time, a 1 + ε stretch approximation for the distance between s and t in the graph G∖F. The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ε for graphs of bounded doubling dimension.