Computing 2-terminal reliability for radio-broadcast networks

The authors present a probabilistic graph model for radio broadcast networks where nodes fail randomly and the edges are perfectly reliable. This model can represent the general case where both the nodes and edges can fail. Using this model, it is shown that the two-terminal reliability problem for...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on reliability 1989-12, Vol.38 (5), p.538-555
Main Authors: AboElFotoh, H.M., Colbourn, C.J.
Format: Article
Language:English
Subjects:
Applied sciences
Computer networks
Costs
Exact sciences and technology
Graph theory
Microwave communication
Mobile communication
Network topology
Radio broadcasting
Radiocommunication specific techniques
Radiocommunications
Reliability theory
Repeaters
Telecommunication network reliability
Telecommunications
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The authors present a probabilistic graph model for radio broadcast networks where nodes fail randomly and the edges are perfectly reliable. This model can represent the general case where both the nodes and edges can fail. Using this model, it is shown that the two-terminal reliability problem for radio broadcast networks is computationally difficult, in particular Hash P-complete, even in two important restricted cases. Efficient bounding techniques based on subgraph counts and vertex-packing methods are presented. The subgraph counting and vertex-packing bounds are the counterparts of the subgraph counting and edge-packing bounds for wired point-to-point networks with reliable nodes and unreliable links. The authors define series and parallel node reductions for arbitrary networks with unreliable nodes and reliable edges, and they incorporate these reductions into a new polynomial-time algorithm to improve the vertex-packing bounds via approximation by series-parallel reducible graphs.< >
ISSN:0018-9529
1558-1721
DOI:10.1109/24.46478