A Distributed Method for Detecting Critical Edges and Increasing Edge Connectivity in Undirected Networks

Abstract

A critical edge is an edge whose removal results in the associated undirected network becoming disconnected. Identifying these critical edges and enhancing the corresponding edge connectivity is critical for achieving robustness in network connectivity. While existing methodologies are effective, they are centralized and rely on global information, which makes them not scalable with respect to the network size or its implementation. To address these shortcomings, a fully distributed approach is introduced in this paper to identify all the critical edges within an undirected network without requiring a central coordinating authority. Computationally, the proposed method has a complexity of O(n), where n is the number of nodes, which is more efficient when compared to the centralized approaches. Furthermore, the proposed method can be used to incrementally increase the network’s edge connectivity to 2, thus addressing the network’s most vulnerable edges.