ylfink@water.UUCP (ylfink) (12/15/86)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
COMPUTER NETWORKS SEMINAR
- Tuesday, December 16, 1986.
Miss Aparna Ramanathan a graduate student of this
department will speak on ``Improving Bounds on All-
terminal Network Reliability''.
TIME: 3:30 PM
ROOM: MC 5158
ABSTRACT
A standard model of a network is a graph in which nodes
represent communication centers and edges represent
links between these centers. Edges are assumed to have
statistically independent probabilities of failure, and
nodes are assumed to be perfectly reliable. The all-
terminal reliability of the network is defined to be
the probability that all the communication centers in
the network are able to communicate with each other in
an environment of random link failures. Exact calcula-
tion of the all-terminal reliability for general graphs
is known to be #P-complete. As a result, much research
has been done in obtaining upper and lower bounds for
all-terminal reliability that avoid the exponential
computation likely to be required by the exact algo-
rithms.
In this talk, two different methods are developed to
improve on the existing bounds. Firstly, a new polyno-
mial time algorithm to count almost minimal cutsets
provides immediate improvement on all of the subgraph
counting bounds. Improvements on the bounds for planar
networks ar also derived.
The second method uses arc-disjoint rooted subdigraphs
of a network to improve on existing lower bounds and
arc-disjoint s-directed cuts for upper bounds. The
-
lower bounds obtained from an arc-packing of acyclic
rooted subdigraphs are shown to be competitive both
with the Kruskal-Katona and Lomonosov-Polesskii bounds.