Resource-sharing systems and hypergraph colorings

Wu-Hsiung Lin, Gerard J. Chang*

*Corresponding author for this work

研究成果: Article同行評審

摘要

A resource-sharing system is modeled by a hypergraph H in which a vertex represents a process and an edge represents a resource consisting of all vertices (processes) that have access to it. A schedule of H=(V,E) is a mapping f:ℕ→2 V, where f(i) is an independent set of H which consists of processes that operate at round i. The rate of f is defined as rate (f)=lim sup n→∞∑ n i=1|f(i)|/(n|V|) , which is the average fraction of operating processes at each round. The purpose of this paper is to study optimal rates for various classes of schedules under different fairness conditions. In particular, we give relations between these optimal rates and fractional/circular chromatic numbers. For the special case of the hypergraph is a connected graph, a new derivation for the previous result by Yeh and Zhu is also given.

原文English
頁(從 - 到)499-508
頁數10
期刊Journal of Combinatorial Optimization
22
發行號4
DOIs
出版狀態Published - 1 十一月 2011

指紋 深入研究「Resource-sharing systems and hypergraph colorings」主題。共同形成了獨特的指紋。

引用此