#### Journal

##### IEEE-ACM TRANSACTIONS ON NETWORKING

Volume -, Issue -, Pages -#### Publisher

##### IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

DOI: 10.1109/TNET.2023.3308142

#### Keywords

Distributed algorithms; articulation points; connected components; critical nodes

#### Ask authors/readers for more resources

This paper introduces two problems, namely identifying the most vital articulation points that significantly impact the network. The first problem aims to find the p most important articulation points that minimize the largest connected component in the remaining network, while the second problem aims to find the p most important articulation points whose removal maximizes the number of partitions in the network. The proposed distributed algorithm shows promising performance compared to a brute force-based exact algorithm.

An articulation point is a node whose removal partitions the network into disconnected segments. The articulation points may affect the reliability and efficiency of wireless multi hop networks from different aspects. Although all articulation points destroy the connectivity of the network, their negative impact on the network is not equal. Removing some articulation points may disconnect a large subset of nodes or generate a large number of partitions, while removing some other articulation points may only disconnect a few nodes. In this paper, we present two novel problems for identifying the most vital articulation points that significantly impact the network. The first problem is finding the p most important articulation points that minimize the largest connected component in the remaining network. The second problem is finding the p most important articulation points whose removal maximizes the number of partitions in the network. We prove that both problems are NP-Hard and propose a distributed algorithm to identify the vital articulation points in both problems. The proposed algorithm establishes a distributed depth-first search tree to identify the articulation points, assigns a score to each articulation point, and selects the prominent articulation points based on their scores. We compare the proposed algorithm with a brute force-based exact algorithm. The simulation result shows that after removing the detected prominent articulation points by the proposed algorithm, the maximum difference between the largest partition size and the number of partitions with the optimal solutions are less than 27.6% and 28.2%, respectively, while the sent bytes of the proposed algorithm can be 89.9% lower.

#### Authors

##### I am an author on this paper

Click your name to claim this paper and add it to your profile.

#### Reviews

#### Recommended

No Data Available