LINK SCHEDULES, FLOWS, AND THE MULTICHROMATIC INDEX OF GRAPHS.

The minimum length of time needed to schedule conversations between stations so that each pair of stations communicates a prespecified length of time and each station communicates with at most one other station at a time is studied. This quantity is a generalization of the multichromatic index of a graph. Two main results are given. Using Edmonds' polytope theorem, it is shown that link scheduling in a multi-hop network with end-to-end demand requirements is limited solely by maximum node degree. Polynomial time algorithm is given to provide an upper bound on minimum schedule length.