Author(s)

Werner Poguntke

Fachbereich Technische Betriebwirtschaft, Fachhochschule Südwestfalen, Hagen, Germany.

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.

Graph Algorithm, Cut, Secret Sharing, Approximation, Network Design

Poguntke, W. (2016) Near-Optimal Placement of Secrets in Graphs. Open Journal of Discrete Mathematics, 6, 238-247. doi: 10.4236/ojdm.2016.64020.