JUCS - Journal of Universal Computer Science 1(9): 633-651, doi: 10.3217/jucs-001-09-0633
An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph
expand article infoR. F. M. Aranha‡, C. Pandu Rangan‡
‡ Indian Institute of Technology, Madras, India, Madras, India

Corresponding author: R. F. M. Aranha

© R. F. M. Aranha, C. Rangan.
This article is freely available under the J.UCS Open Content License.
Citation: Aranha RFM, Rangan CP (1995) An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph. JUCS - Journal of Universal Computer Science 1(9): 633-651. https://doi.org/10.3217/jucs-001-09-0633
Open Access
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, st-numbering, biconnected graph