ylfink@water.waterloo.edu (ylfink) (02/05/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
NETWORK RELIABILITY SEMINAR
- Wednesday, February 10, 1988
Mr. Louis D. Nel, a graduate student of this
department, will speak on ``Locating a Broadcast
Facility in an Unreliable Network''.
TIME: 2:00 PM
ROOM: MC 5158A
ABSTRACT
A model of a communication network is a probabilistic
graph in which each edge has an independent probability
of being operational. The broadcast Facility Location
(BFL) problem is to identify a node such that the
expected number of nodes connected to it in the
presence of random edge failures is as large as
possible. This problem is NP-hard and hence we are
interested in approximate solutions which can be
determined in polynomial time. We present a location
strategy based on efficiently computable two-terminal
network reliability bounds. This strategy does not
guarantee to find an optimal node but instead finds a
set of good nodes by eliminating nodes which cannot be
optimal locations. Computational experience is
reported for a network with 20 nodes and 31 edges.