An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph

R. F. M. Aranha (Indian Institute of Technology, Madras, India, India)

C. Pandu Rangan (Indian Institute of Technology, Madras, India, India)

Abstract: Given a biconnected network G with n nodes and a specific edge (r, s) of G, the st-numbering problem asks for an assignment of integers to the nodes satisfying the following condition: r is assigned the number 1 and s is assigned the number n and all other nodes are assigned numbers in such a way that every node (other than r and s) has a neighbour with smaller st-number and a neighbour with larger st-number. Since st-numbering exists iff G is biconnected, it serves as a powerful "local characterization" of the "global" property of the network. We present an efficient O(e) message complexity and O(n) time complexity algorithm for st-numbering a biconnected graph.

Keywords: Distributed graph algorithms, biconnected graph, st-numbering

Categories: G.2.2