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.
|Original language||English (US)|
|Number of pages||5|
|State||Published - Dec 1 1984|
ASJC Scopus subject areas