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

Research output: Contribution to conferencePaperpeer-review

Abstract

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 languageEnglish (US)
Pages498-502
Number of pages5
StatePublished - Dec 1 1984

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'LINK SCHEDULES, FLOWS, AND THE MULTICHROMATIC INDEX OF GRAPHS.'. Together they form a unique fingerprint.

Cite this