.png){kind=icon}
.png){kind=icon}
Return
A random searching algorithm for efficiently solving the connectivity-oriented robust optimization problem on large-scale networked systems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2025.112924.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
By consolidating part of the links to be invulnerable, there will be no connectivity degradation in a network under expected network failure intensity. Although existing link consolidation methods can handle large-scale networks, their solutions are far from optimal. Redundancy in existing solutions can be quantified by the connectivity of the pure graph consisting of the necessary subset of links, and existing methods improve pure graph connectivity to far above the expected value. Fortunately, we have found a special superset of link cuts, and proved that it can reduce consolidation links by removing the right set of links from existing solutions while maintaining the desired connectivity. In response to the high complexity of searching for the optimal superset, we found one kind of superset that is close to the optimal solution and easy to locate, significantly reducing the number of links that need to be consolidated with a slight increase in preprocessing overhead. Experiments have shown that in large networks, the algorithm can provide a protection effect of over 99.9%, and can lead to 60% overhead savings compared to existing high-speed algorithms under the same computing time. On small-scale networks where the optimal algorithm is feasible, the average additional cost compared to the optimal result can be controlled within 1%. Thus, while ensuring accuracy, it can further approach the optimal solution compared to existing algorithms, significantly reducing the overhead of infrastructure consolidation.
Keywords:
Connectivity
Disjoint cut collection
Pure graph
Link consolidation
Approximation method
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W
Organization
No organization information available