TY - JOUR

T1 - A connection between circular colorings and periodic schedules

AU - Yeh, Hong Gwa

N1 - Funding Information:
The author thanks anonymous referees for very careful reading and for many constructive comments which helped to considerably improve the presentation of the paper. The author was partially supported by National Science Council of ROC under grant NSC94-2115-M-008-015.

PY - 2009/4/6

Y1 - 2009/4/6

N2 - We show that there is a curious connection between circular colorings of edge-weighted digraphs and periodic schedules of timed marked graphs. Circular coloring of an edge-weighted digraph was introduced by Mohar [B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107-116]. This kind of coloring is a very natural generalization of several well-known graph coloring problems including the usual circular coloring [X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371-410] and the circular coloring of vertex-weighted graphs [W. Deuber, X. Zhu, Circular coloring of weighted graphs, J. Graph Theory 23 (1996) 365-376]. Timed marked graphs over(G, →) [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAM J. Appl. Math. 14 (1966) 1390-1411] are used, in computer science, to model the data movement in parallel computations, where a vertex represents a task, an arc u v with weight cu v represents a data channel with communication cost, and tokens on arc u v represent the input data of task vertex v. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if u v is an out-arc of u, then at time t + cu v vertex u places one token on arc u v. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {fu (1), fu (2), fu (3), ...} such that vertex u starts its kth operation at time fu (k) and each in-arc of u contains at least one token at that time. The set of functions {fu : u ∈ V (over(G, →))} is called a schedule of over(G, →). Computer scientists are particularly interested in periodic schedules. Given a timed marked graph over(G, →), they ask if there exist a period p > 0 and real numbers xu such that over(G, →) has a periodic schedule of the form fu (k) = xu + p (k - 1) for each vertex u and any positive integer k. In this note we demonstrate an unexpected connection between circular colorings and periodic schedules. The aim of this note is to provide a possibility of translating problems and methods from one area of graph coloring to another area of computer science.

AB - We show that there is a curious connection between circular colorings of edge-weighted digraphs and periodic schedules of timed marked graphs. Circular coloring of an edge-weighted digraph was introduced by Mohar [B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107-116]. This kind of coloring is a very natural generalization of several well-known graph coloring problems including the usual circular coloring [X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371-410] and the circular coloring of vertex-weighted graphs [W. Deuber, X. Zhu, Circular coloring of weighted graphs, J. Graph Theory 23 (1996) 365-376]. Timed marked graphs over(G, →) [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAM J. Appl. Math. 14 (1966) 1390-1411] are used, in computer science, to model the data movement in parallel computations, where a vertex represents a task, an arc u v with weight cu v represents a data channel with communication cost, and tokens on arc u v represent the input data of task vertex v. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if u v is an out-arc of u, then at time t + cu v vertex u places one token on arc u v. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {fu (1), fu (2), fu (3), ...} such that vertex u starts its kth operation at time fu (k) and each in-arc of u contains at least one token at that time. The set of functions {fu : u ∈ V (over(G, →))} is called a schedule of over(G, →). Computer scientists are particularly interested in periodic schedules. Given a timed marked graph over(G, →), they ask if there exist a period p > 0 and real numbers xu such that over(G, →) has a periodic schedule of the form fu (k) = xu + p (k - 1) for each vertex u and any positive integer k. In this note we demonstrate an unexpected connection between circular colorings and periodic schedules. The aim of this note is to provide a possibility of translating problems and methods from one area of graph coloring to another area of computer science.

KW - Circular chromatic number

KW - Edge-weighted graph

KW - Minty's theorem

KW - Periodic scheduling

KW - Timed marked graph

UR - http://www.scopus.com/inward/record.url?scp=62149098496&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.10.003

DO - 10.1016/j.dam.2008.10.003

M3 - 期刊論文

AN - SCOPUS:62149098496

SN - 0166-218X

VL - 157

SP - 1663

EP - 1668

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 7

ER -