Minimum-Time Broadcast under Edge-Disjoint Paths Modes
Pierre Fraigniaud · 2008
This paper aims to study broadcast and multicast communication prob-lems in networks under several variants of the edge-disjoint path mode. We derive upper and lower bounds for the approximability ratios of these prob-lems (i.e., the worst-case ratios of the time required for a protocol computed in polynomial time to complete, over the time of an optimal protocol). These bounds show that slight modifications of the model (graphs vs. digraphs, all-port vs. single port, standard regimen vs. restricted regimen, etc.) have a tremendous impact on the difficulty, and of course on the complexity, of the problems. 1