Loading...
Please wait, while we are loading the content...
Similar Documents
Minimum-Time Broadcast under Edge-Disjoint Paths Modes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fraigniaud, Pierre |
| Copyright Year | 2008 |
| Abstract | This paper aims to study broadcast and multicast communication problems in networks under several variants of the edge-disjoint path mode. We derive upper and lower bounds for the approximability ratios of these problems (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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.lri.fr/~pierre/POSTSCRIPTS/fun01.ps |
| Alternate Webpage(s) | http://www.liafa.univ-paris-diderot.fr/~pierref/MPRI/fun01.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
