TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1999

COGA 5-Wheel

Page Content

to Navigation

Preprints 1999

A Simple Approximation Algorithm for Scheduling Forests with Unit Processing Times and Zero-One Communication Delays
Citation key Report-506-1996
Author Rolf H. Möhring and Markus W. Schäffter
Year 1996
Number 506
Note Integrated into Scheduling series-parallel orders subject to 0/1 communication delays, Parallel Computing (1999) 23-40
Institution Technische Universität Berlin, Institut für Mathematik
Abstract In the last few years, scheduling jobs due to communication delays has received a great deal of attention. We consider the problem of scheduling forests due to unit processing times and zero-one communication delays and focus on the approximation algorithm of Hanen and Munier and on the algorithm of Guinand, Rapine and Trystram. These algorithms and their analysis are quite complex. In contrast, we present a very simple list scheduling algorithm for the problem $P|\textit{prec=tree,\
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe