The optimal average information ratio of secret-sharing schemes for the access structures based on unicycle graphs and bipartite graphs

Hui Chuan Lu*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In this paper, we derive bounds on the optimal average information ratio of the access structures based on general graphs and investigate the value of the ratio for unicycle graphs and some bipartite graphs. We determine the exact values of this ratio for some infinite classes of bipartite graphs and unicycle graphs. This extends previous results. We also provide good bounds on the optimal average information ratio for all unicycle graphs.

Original languageEnglish
Pages (from-to)131-142
Number of pages12
JournalDiscrete Applied Mathematics
Volume233
DOIs
StatePublished - 31 Dec 2017

Keywords

  • Average information ratio
  • Bipartite graph
  • Complete multipartite covering
  • Fractional star covering
  • Maximum independent set
  • Secret-sharing scheme
  • Star decomposition
  • Unicycle graph

Fingerprint Dive into the research topics of 'The optimal average information ratio of secret-sharing schemes for the access structures based on unicycle graphs and bipartite graphs'. Together they form a unique fingerprint.

Cite this