WORST-CASE ANALYSIS OF LAWLERS ALGORITHM FOR SCHEDULING TREES WITH COMMUNICATION DELAYS

Authors
GUINAND F RAPINE C TRYSTRAM D
Citation
F. Guinand et al., WORST-CASE ANALYSIS OF LAWLERS ALGORITHM FOR SCHEDULING TREES WITH COMMUNICATION DELAYS, IEEE transactions on parallel and distributed systems, 8(10), 1997, pp. 1085-1086
Citations number
3
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
8
Issue
10
Year of publication
1997
Pages
1085 - 1086
Database
ISI
SICI code
1045-9219(1997)8:10<1085:WAOLAF>2.0.ZU;2-7
Abstract
This paper establishes the exact upper bound for Lawler's heuristic pr oving that its schedule of a UECT tree on m identical processors does not exceed an optimal solution by more than m/2 time units.