Brahim Hamid and Bertrand Le Saec and Mohamed Mosbah
Distributed 2Vertex Connectivity Test of Graphs Using Local Knowledge
533 - 538
2007
1
3
International Journal of Computer and Information Engineering
https://publications.waset.org/pdf/9362
https://publications.waset.org/vol/3
World Academy of Science, Engineering and Technology
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 2connected 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 semianonymous Only the root of the preconstructed spanning tree needs to be identified.
Open Science Index 3, 2007