Call scheduling in trees, rings and meshes

The problem of establishing and completing a given set of calls as early as possible is studied for bidirectional and directed calls in various classes of networks. Even under the assumption of unit bandwidth requirements and unit call durations, call scheduling is NP-hard for trees with unbounded degree, for rings, and for meshes. Whereas bidirectional calls can be scheduled optimally in polynomial time for trees of constant degree, the problem for directed calls is already NP-hard for binary trees. Approximation algorithms with a constant performance ratio are known for many NP-hard variants of call scheduling.