Polynomial-Time Topological Reductions That Preserve the Diameter Constrained Reliability of a Communication Network

We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may l...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on reliability 2011-12, Vol.60 (4), p.845-851
Main Authors: Cancela, H., El Khadiri, M., Petingi, L. A.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Computer network reliability
Diameter constraint
edge decomposition
factoring
network reliability
Network topology
NP-hard problem
paths
Peer to peer computing
topological reductions
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:We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. For illustration, we integrate this algorithm within an exact recursive factorization approach based upon Moskowitz's edge decomposition. Experiments conducted on different real-world topologies confirmed a substantial computational gain, except when highly-dense graphs were tested.
ISSN:0018-9529
1558-1721
DOI:10.1109/TR.2011.2170250