Link Scheduling in Polynomial Time

Bruce Hajek, Galen Sasaki

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)910-917
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - Sep 1988

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Link Scheduling in Polynomial Time'. Together they form a unique fingerprint.

Cite this