The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width Original Research Article

The one-way and two-way communication modes used for sending messages to processors of interconnection networks via vertex-disjoint paths in one communication step are investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). This paper reveals a direct relationship between the gossip complexity and the vertex bisection width. More precisely, the main results are the following: