A Greedy Algorithm for Faster Feasibility Evaluation of All-Terminal-Reliable Networks

Area of Science:

• Computer Science
• Network Reliability Engineering
• Operations Research

Background:

• Calculating the all-terminal reliability (ATR) of stochastic networks is computationally intensive.
• Existing methods often require extensive computation, making it difficult to quickly assess network performance against a target reliability.
• Efficiently determining if a network's ATR exceeds a preset value is crucial for practical applications.

Purpose of the Study:

• To develop a computationally efficient method for determining if a network's all-terminal reliability (ATR) meets a specified threshold.
• To introduce a novel approach based on sequential lower and upper bound generation using greedy network factoring.
• To compare the performance of different greedy algorithm implementations for ATR bound calculation.

Main Methods:

• The study proposes a greedy network factoring method to generate sequential lower and upper bounds for ATR.
• The process involves identifying the most reliable spanning tree and the most unreliable cut set.
• These elements' probabilities are used to update ATR bounds recursively on subnetworks until the threshold is met.

Main Results:

• The proposed method rapidly converges, allowing for early decisions on network feasibility.
• Computer experiments compared various greedy algorithm implementations.
• Performance variations were observed based on network characteristics like layout and edge probabilities.

Conclusions:

• The greedy network factoring approach provides an efficient way to estimate ATR bounds.
• The method significantly reduces the computational effort required to assess network reliability against a target value.
• Understanding the relationship between network characteristics and algorithm performance can guide implementation selection.