Mathematical Problems in Engineering
Volume 4 (1998), Issue 3, Pages 247-266
doi:10.1155/S1024123X98000817
Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula
1Department of Mathematics and Computer Science, Seton Hall University, South Orange 07079, NJ, USA
2Department of Computer and Information Science, New Jersey Institute of Technology, Newark 07102, NJ, USA
Received 12 August 1996; Revised 15 October 1996
Copyright © 1998 Thomas J. Marlowe and Laura Schoppmann. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Reliability is an important consideration in analyzing computer and other communication networks, but current techniques are extremely limited in the classes of graphs which can be analyzed efficiently. While Gilbert's formula establishes a theoretically elegant recursive relationship between the edge reliability of a graph and the reliability of its subgraphs, naive evaluation requires consideration of all sequences of deletions of individual vertices, and for many graphs has time complexity essentially
Θ
(N!). We discuss a general approach which significantly reduces complexity, encoding subgraph isomorphism in a finer partition by invariants, and recursing through the set of invariants.
We illustrate this approach using threshhold graphs, and show that any computation of reliability using Gilbert's formula will be polynomial-time if and only if the number of invariants considered is polynomial; we then show families of graphs with polynomial-time, and non-polynomial reliability computation, and show that these encompass most previously known results.
We then codify our approach to indicate how it can be used for other classes of graphs, and suggest several classes to which the technique can be applied.