Resource-sharing system scheduling and circular chromatic number

Hong Gwa Yeh, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Circular chromatic number and scheduling for a resource-sharing system was studied. It was proved that the rate of an optimal strongly fair scheduling of a graph G is equal to the reciprocal of the circular chromatic number of G. The rate of an optimal weakly fair scheduling of G was proved to be equal to the reciprocal of the fractional chromatic number of g. In the study of circular chromatic number, the target graph for the interleaved p-color, q-tuple coloring and the target graph of Bondy and Hell defined (p, q)-coloring were found to be homomorphically equivalent.

Original languageEnglish
Pages (from-to)447-460
Number of pages14
JournalTheoretical Computer Science
Issue number1-3
StatePublished - 28 Feb 2005


  • Circular chromatic number
  • Fairness
  • Fractional chromatic number
  • Homomorphism
  • Minimum mean cycle
  • Scheduling
  • Scheduling by edge reversal


Dive into the research topics of 'Resource-sharing system scheduling and circular chromatic number'. Together they form a unique fingerprint.

Cite this