2013/02/19 by László Csirmaz, Gábor Tardos, Csirmaz, L. +1
Computer Science · #05B40 #05C85 #94A60 #94A62 #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #E.3 #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1302.4609
openalex publication_date 2013/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 1/(2-1/c), 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.