ylfink@water.UUCP (07/03/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
COMBINATORIAL ALGORITHMS SEMINAR
- Tuesday, July 7, 1987
Mr. Hosam Aboel Fotoh a graduate student of this
department will speak on ``Computing Reliability
Measures for Radio Broadcast Networks''.
TIME: 2:30 PM
ROOM: MC 6091A
ABSTRACT
An alternative to wired point-to-point computer and
communication networks is radio broadcasting. In radio
broadcast networks each site is equipped with a radio
transmitter/receiver with a specified range. Every site
communicates with other sites by broadcasting the
messages to all other sites within its transmitter
range. In an environment where some network sites fail
randomly, the network reliability is an important
issue. In this talk we present a probabilistic graph
model for radio broadcast networks, and use this model
to formulate some reliability and performance measures.
These measures include two-terminal reliability and
k-terminal reliability (connectivity), the probability
of reaching a destination node or a set of destination
nodes by the mth transmission. We also discuss the
computational complexity of these measures. In
particular we show that the two-terminal reliability is
#P-complete.