Adaptation of the breadth first search algorithm for cut-edge detection in wireless multihop networks
Bratislav Milić, Miroslaw Malek · 2007
We extend the Breadth First Search (BFS) algorithm to use it for cut-edge(bridge) detection in graphs. The changes in the algorithm are tailored such that the algorithm can be applied in wireless multihop networks: e.g., it fully utilizes the broadcasting nature of the wireless medium. The distributed BFS algorithm (flooding) is widely used for route discovery and information dissemination in wireless multihop networks (WMNs) so the overhead introduced by our bridge detection algorithm is limited - the network is already performing the distributed BFS and we reuse the information from it to detect the bridges.