TITLE:
Near-Optimal Placement of Secrets in Graphs
AUTHORS:
Werner Poguntke
KEYWORDS:
Graph Algorithm, Cut, Secret Sharing, Approximation, Network Design
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.6 No.4,
September
2,
2016
ABSTRACT: We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.