科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G = (V, E) be an undirected graph and let S subset of V. The S-connectivity lambda(S)(G)(u, v) of u, v is an element of V is the maximum number of uv-paths that no two of them have an edge or a node in S \ {u, v} in common. Edge-connectivity is the case S = empty set and node-connectivity is the case S = V. Given an integer k and a subset T subset of V of terminals, we consider the problem of assigning small "labels" (binary strings) to the terminals, such that given the labels of two terminals u, v is an element of T, one can decide whether lambda(S)(G)(u, v) >= k (k-partial labeling scheme) or to return min{lambda(S)(G) (u, v), k} (k-full labeling scheme). We observe that the best known labeling schemes for edge-connectivity (the case S = empty set) extend to element-connectivity (the case S subset of V \ T), and use it to obtain a simple k-full labeling scheme for node-connectivity (the case S = V). If q distinct queries are expected, our k-full scheme has max-label size O(k log(2) vertical bar T vertical bar logq), with success probability 1 - 1/q for all queries. We also give a deterministic k-full labeling scheme with max-label size O(k log(3) vertical bar T vertical bar). Recently, Hsu and Lu (2009) [6] gave an optimal O(k log vertical bar T vertical bar) labeling scheme for the k-partial case. This implies an O(k(2) log vertical bar T vertical bar) labeling scheme for the k-full case. Our deterministic k-full labeling scheme is better for k = Omega(log(2) vertical bar T vertical bar).
- 出版日期2012-1-15
