Previous results Problem Collision Graph Completion detection time RB Without Bidirectional O(n) Arbitrary O(nlogn) RG Without Strongly connected On3/2 arb Without Bidirectional Unsolvable With Bidirectional O(n Bidirectional O(recc) Strongly connected n·eCC n:number of nodes, r: length of message, ecc: largest distance from the source
Previous results Problem Collision detection Graph Completion time RB Without Bidirectional O(n) Arbitrary O(nlog2n) RG Without Strongly connected O(n 3/2) ARB Without Bidirectional Unsolvable With Bidirectional O(n) Bidirectional O(r+ecc) Strongly connected O(n・ecc) n: number of nodes, r: length of message, ecc: largest distance from the source
P revious and our results Problem Collision GI rap h Completion detection time arb Without Bidirectional Unsolvable arB Without Bidirectional(n22) Strongly connected(n22) O(n32) aRG Without Bidirectional (n22) O(nlogn) Strongly connected(n22) O(n3/2 n: number of nodes Our results
Previous and our results Problem Collision detection Graph Completion time ARB Without Bidirectional Unsolvable ARB Without Bidirectional (n≥2) O(n) Strongly connected (n≥2) O(n 3/2) ARG Without Bidirectional (n≥2) O(nlog3n) Strongly connected (n≥2) O(n 3/2) n: number of nodes Our results
Conventional algorithm(Round robin phase k(2k segments, 1 segment =2 rounds The node with id i acts as a transmitter in round i 4
Conventional algorithm (Round Robin) phase k ( 2 k segments, 1 segment = 2 k rounds ) 1 2 4 5 10 7 8 11 The node with ID i acts as a transmitter in round i. 12
Conventional algorithm(Round robin phase k(2k segments, 1 segment =2 rounds The node with id i acts as a transmitter in round i phase_l · segment1 round round 2 Phase segment 2 round1D≤2 4 round 2 node which received a message transmitter
1 2 4 5 10 7 8 11 12 phase 1 round 1 round 2 Phase 1 ID≤2 1 • segment 1 Conventional algorithm (Round Robin) phase 1 round 1 round 2 • segment 2 phase k ( 2 k segments, 1 segment = 2 k rounds ) : node which received a message : transmitter The node with ID i acts as a transmitter in round i
Conventional algorithm(Round robin phase k(2k segments, 1 segment =2 rounds The node with id i acts as a transmitter in round i phase 2 · segment1 round round 2 Phase 2 round 3 round 4 ID≤2 4 node which received a message :transmitter
1 2 4 5 10 7 8 11 12 Phase 2 ID≤2 2 phase 2 round 1 round 2 round 3 round 4 • segment 1 Conventional algorithm (Round Robin) phase 2 phase k ( 2 k segments, 1 segment = 2 k rounds ) : node which received a message : transmitter The node with ID i acts as a transmitter in round i