Paper Info
Title
Distributed local 2-connectivity test of graphs and applications
Abstract
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 constructive approach. The contribution of this paper is threefold. First, using a pre-constructed 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 and 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. Moreover, we investigate some applications that can use our protocol as a pre-processing task for initial configurations.
Year
DOI
Venue
2007
10.1007/978-3-540-74742-0_20
ISPA
Keywords
Field
DocType
constructive approach,vertex connectivity,initial configuration,vertex connectivity test,graph g,considered graph,last contribution,local knowledge,following requirement,smallest number,2-connectivity test,spanning tree,distributed environment,message passing
Line graph,Computer science,Graph factorization,Vertex (graph theory),Cycle graph,Spanning tree,Windmill graph,Butterfly graph,Complement graph,Distributed computing
Conference
Volume
ISSN
ISBN
4742
0302-9743
3-540-74741-9
Citations 
PageRank 
References 
1
0.36
9
Authors
3
Name
Order
Citations
PageRank
Brahim Hamid113624.73
Bertrand Le Saëc210616.83
Mohamed Mosbah341562.79