The complexity of path coloring and call scheduling

Modern high-performance communication networks pose a number of challenging problems concerning the efficient allocation of resources to connection re quests. In all-optical networks with wavelength-division multiplexing, conn ection requests must be assigned paths and colors (wavelengths) such that i ntersecting paths receive different colors, and the goal is to minimize the number of colors used. This path coloring problem is proved. N P-hard for undirected and bidirected ring networks. Path coloring in undirected tree n etworks is shown to be equivalent to edge coloring of multigraphs, which im plies a polynomial-time optimal algorithm for trees of constant degree as w ell as N P-hardness and an approximation algorithm with absolute approximat ion ratio 4/3 and asymptotic approximation ratio 1.1 for trees of arbitrary degree. For bidirected trees, path coloring is shown to be N P-hard even i n the binary case. A polynomial-time optimal algorithm is given for path co loring in undirected or bidirected trees with n nodes under the assumption that the number of paths touching every single node of the tree is O((log n )(1-epsilon)). Call scheduling is the problem of assigning paths and starti ng times to calls in a network with bandwidth reservation such that the max imum completion time is minimized. In the case of unit bandwidth requiremen ts, unit edge capacities, and unit call durations, call scheduling is equiv alent to path coloring. If either the bandwidth requirements or the call du rations can be arbitrary, call scheduling is shown N P-hard for virtually e very network topology. (C) 2001 Elsevier Science B.V. All rights reserved.