ALCOMFT-TR-02-90

Thomas Lücking, Burkhard Monien and Manuel Rode
On the Problem of Scheduling Flows on Distributed Networks
Paderborn. Work package 2. May 2002.

Abstract: We consider the problem of scheduling a given flow on a synchronous distributed network. This problem arises using diffusion-based approaches to compute a balancing flow, which has to be scheduled afterwards. We show that every distributed scheduling strategy requires at least 3/2 times the minimum number of rounds. Furthermore we give a distributed algorithm for flows on tree networks, which requires at most two times the optimal number of rounds.

Postscript file: ALCOMFT-TR-02-90.ps.gz (90 kb).