Distributed 2-Vertex Connectivity Test of Graphs Using Local Knowledge

The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a general and a constructive approach. The contribution of this paper is threefold. First, using a preconstructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph G, where M is the number of its edges, N the number of its nodes and Δ is its degree, our algorithms need the following requirements: The first one uses O(Δ×N2) steps and O(Δ×logΔ) bits per node. The second one uses O(Δ×N2) messages, O(N2) time and O(Δ × logΔ) bits per node. Furthermore, the studied network is semi-anonymous: Only the root of the pre-constructed spanning tree needs to be identified.

• Brahim Hamid
• Bertrand Le Saec
• Mohamed Mosbah

• Distributed computing
• fault-tolerance
• graph relabeling systems
• local computations
• local knowledge
• message passing system
• networks
• vertex connectivity.

[1] M. Bahramgiri, M.T. Hajiaghayi, and V.S. Mirrokni. Fault-tolerant and
3-dimensional distributed topology control algorithms in wireless multihop
networks. In In IEEE Int. Conf. on Computer Communications and
Networks (ICCCN02), pages 392-397, 2002.
[2] A. H. Esfahanian and S.L. Hakimi. On computing the connectivities of
graphs and digraphs. Networks, pages 355-366, 1984.
[3] S. Even and R. E. Tarjan. Network flow and testing graph connectivity.
SIAM Journal on Computing, 4(4):507-518, 1975.
[4] H.N. Gabow. Using expander graphs to find vertex connectivity. In 41st Annual Symposium on Foundations of Computer Science, page 410, 2000.
[5] M. R. Henzinger, S. Rao, and H. N. Gabow. Computing vertex
connectivity: new bounds from old techniques. J. Algorithms, 34(2):222-
250, 2000.
[6] I. Litovsky, Y. M'etivier, and E. Sopena. Graph relabeling systems and
distributed algorithms. In World Scientific Publishing, editor, Handbook
of graph grammars and computing by graph transformation, volume
Vol. III, Eds. H. Ehrig, H.J. Kreowski, U. Montanari and G. Rozenberg,
pages 1-56, 1999.
[7] Y. M'etivier, M. Mosbah, and A. Sellami. Proving distributed algorithms
by graph relabeling systems: Example of tree in networks with processor
identities. In applied Graph Transformations (AGT2002), Grenoble,
April 2002.
[8] R. De Prisco, B. Lampson, and N. Lynch. Revisiting the paxos
algorithm. In Lecture Notes in Computer Science: Distributed Algorithms,
Proc. of 11th International Workshop, WDAG-97, Saarbr¨ucken,
Germany, volume 1320, pages 111-125. Springer, sep 1997.
[9] R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM
Journal on Computing 1, pages 146-160, 1972.
[10] G. Tel. Introduction to distributed algorithms. Cambridge University
Press, second edition, 2000.
[11] K. Wada and W. Chen. Optimal fault-tolerant routings with small routing
tables for k-connected graphs. J. Discrete Algorithms, 2(4):517-530,
2004.
[12] D. West. Introduction to graph theory. Second edition. Prentice-Hall,
2nd ed. edition, 2001.