Link Scheduling in Polynomial Time

Two polynomial time algorithms are given for scheduling conversations in a spread spectrum radio network. The constraint on conversations is that each station can converse with at most one other station at a time. The first algorithm is strongly polynomial and finds a schedule of minimum length which allows each pair of neighboring stations to directly converse for a prescribed length of time. The second algorithm is designed for the situation in which messages must be relayed multiple hops. The algorithm produces, in polynomial time, a routing vector and compatible link schedule which jointly meet a prespecified end-to-end demand, such that the schedule has the smallest possible length.