کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427272 | 686479 | 2012 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A note on labeling schemes for graph connectivity A note on labeling schemes for graph connectivity](/preview/png/427272.png)
Let G=(V,E)G=(V,E) be an undirected graph and let S⊆VS⊆V. The S -connectivity λGS(u,v) of u,v∈Vu,v∈V is the maximum number of uv -paths that no two of them have an edge or a node in S∖{u,v}S∖{u,v} in common. Edge-connectivity is the case S=∅S=∅ and node-connectivity is the case S=VS=V. Given an integer k and a subset T⊆VT⊆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∈Tu,v∈T, one can decide whether λGS(u,v)⩾k (k -partial labeling scheme) or to return min{λGS(u,v),k} (k -full labeling scheme). We observe that the best known labeling schemes for edge-connectivity (the case S=∅S=∅) extend to element-connectivity (the case S⊆V∖TS⊆V∖T), and use it to obtain a simple k -full labeling scheme for node-connectivity (the case S=VS=V). If q distinct queries are expected, our k -full scheme has max-label size O(klog2|T|logq), with success probability 1−1q for all queries. We also give a deterministic k -full labeling scheme with max-label size O(klog3|T|)O(klog3|T|). Recently, Hsu and Lu (2009) [6] gave an optimal O(klog|T|)O(klog|T|) labeling scheme for the k -partial case. This implies an O(k2log|T|)O(k2log|T|) labeling scheme for the k-full case. Our deterministic k -full labeling scheme is better for k=Ω(log2|T|)k=Ω(log2|T|).
► Let κuvκuv denote the uv -node-connectivity in a graph G=(V,E)G=(V,E) and let k be an integer.
► We consider assigning small node labels so that any u,v∈Vu,v∈V can compute min{κuv,k}min{κuv,k}.
► Our max-label size is O(klog3|V|)O(klog3|V|).
► For k=Ω(log2|V|)k=Ω(log2|V|) this improves the known bound O(k2log|V|)O(k2log|V|).
Journal: Information Processing Letters - Volume 112, Issues 1–2, 15 January 2012, Pages 39–43