Call Scheduling in Trees, Rings and Meshes
Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS-30), 1997
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 constant performance ratio are known
for many NP-hard variants of call scheduling.
