An efficient distributed algorithm for finding all hinge vertices in networks

Abstract

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 ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.

Keywords:

• Distributed systems
• Distributed algorithms
• Hinge vertices
• Static asynchronous networks
• Graph algorithms

Acknowledgements

This research was partially supported by the National Science Council of Taiwan (grant NSC93-2115-M-141-001).