Optimal algorithms for broadcast and gossip in the edge-disjoint path modes

The communication power of the one-way and two-way edge-disjoint path modes for broadcast and gossip is investigated. the complexity of communication algorithms is measured by the number of communication steps (rounds), the main results achieved are the following: 1. For each connected graph G(n) of n nodes, the complexity of broad cast in G(n), B-min(G(n))(r) satisfies [log(2)n] less than or equal to B-min(G(n)) less than or equal to [log(2)n] + 1. The complete binary trees meet the upper bound, and all graphs containing a Hamiltonian path meet the lower bound. 2. For each connected graph G(n) of n nodes, the one-way (two-way) gossip complexity R(G(n)) (R(2)(G(n))) satisfies [log(2)n] less than or equal to R(2)(G(n)) less than or equal to 2 .[log(2)n] + 1, 1.44...log(2)n less than or equal to R(G(n)) less than or equal to 2 .[log(2)n] + 2. All these lower and upper bounds are shown to be sharp up to 1.