mwang@watmath.UUCP (mwang) (07/12/83)
_D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E
_U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O
_S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S
_S_Y_S_T_E_M_S _S_E_M_I_N_A_R
- Tuesday, July 19, 1983.
Dr. C.J. Colbourn of the University of Saskatchewan
will speak on ``The Construction of Reliable Series-
Parallel Networks''.
TIME: 1.30 PM
ROOM: MC 5158
ABSTRACT
The design of reliable computer communications networks
is a topic of significant interest; many heuristic
methods have been developed for producing reliable net-
works. Perhaps the most widely used measure of relia-
bility is a probabilistic one: the probability that the
network remains connected in an environment of (sta-
tistically independent) link failures. In this talk,
we characterize the series-parallel networks which are
most reliable with respect to this probabilistic meas-
ure. Remarkably enough, the most reliable series-
parallel networks have a simple characterization in
terms of degrees; in particular, the characterization
is independent of many typical reliability estimates
such as connectivity and diameter. The characteriza-
tion is derived by solving a recurrence relation giving
the number of connected subnetworks of series-parallel
networks.
July 12, 1983