Path: utzoo!utgpu!water!ylfink
From: ylfink@water.waterloo.edu (ylfink)
Newsgroups: ont.events,uw.talks
Subject: Locating a Broadcast Facility in an Unreliable Network.
Keywords: Mr. Louis D. Nel, Wed., Feb. 10/88, 2:00 PM, MC 5158A.
Message-ID: <1401@water.waterloo.edu>
Date: 4 Feb 88 19:30:59 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 35



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.