Optimal multiple interval assignments in frequency assignment and traffic phasing

In this paper, we consider the optimal assignments of unions of intervals to the vertices of the compatibility graph G, which arises in connection with frequency assignment and traffic phasing problems. It is shown that the optimal multiple interval phasing numbers θ_J≥rx(G) and θ^J≥r_xN(G), are optimal solutions to linear programming problems whose variables correspond to maximal cliques of G. Efficient algorithms are given for determining the first number, θ_J≥rx(G), when G is a chordal graph or a transitively orientable graph.