Name
Abstract | ||
|---|---|---|
The information rate for an access structure is the reciprocal of the load of the optimal secret sharing scheme for this structure. We determine this value for all trees: it is $(2-1/c)^{-1}$, where $c$ is the size of the largest core of the tree. A subset of the vertices of a tree is a core if it induces a connected subgraph and for each vertex in the subset one finds a neighbor outside the subset. Our result follows from a lower and an upper bound on the information rate that applies for any graph and happen to coincide for trees because of a correspondence between the size of the largest core and a quantity related to a fractional cover of the tree with stars. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TIT.2012.2236958 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
graph theory,information theory,security of data,access structure,core,optimal information rate,secret sharing scheme,subgraph,trees,Entropy method,fractional packing and cover,graph,information rate,secret sharing scheme | Journal | 59 |
Issue | ISSN | Citations |
4 | 0018-9448 | 3 |
PageRank | References | Authors |
0.40 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| László Csirmaz | 1 | 163 | 15.86 |
| Gábor Tardos | 2 | 1261 | 140.58 |