An efficient distributed algorithm for finding all hinge vertices in networks.

Let G =( V , E ) be a graph with vertex set V of size n and edge set E of size m . A vertex v ? V is called a hinge vertex if there exist two vertices in V \{ v } such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O ( n 2 ) time complexity and O ( m ) message complexity. In particular, the total messages exchanged during the algorithm are at most 2 m (log n + n log n +1) bits. [ABSTRACT FROM AUTHOR]