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.