English  |  正體中文  |  简体中文  |  Items with full text/Total items : 66984/66984 (100%)
Visitors : 23023237      Online Users : 108
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/27934


    Title: A connection between circular colorings and periodic schedules
    Authors: Yeh,HG
    Contributors: 數學研究所
    Keywords: STAR CHROMATIC NUMBER;PARALLEL COMPUTATIONS;WEIGHTED GRAPHS;SYSTEMS
    Date: 2009
    Issue Date: 2010-06-29 19:38:22 (UTC+8)
    Publisher: 中央大學
    Abstract: 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 (G) over right arrow [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAMJ. 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 nu with weight c(u nu) represents a data channel with communication cost, and tokens on arc u nu represent the input data of task vertex nu. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if u nu is an out-arc of u, then at time t + c(u nu) vertex u places one token on arc u nu. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {f(u)(1),f(u)(2),f(u)(3),...} such that vertex u starts its kth operation at time f(u)(k) and each in-arc of u contains at least one token at that time. The set of functions {f(u) : u is an element of V((G) over right arrow)} is called a schedule of (G) over right arrow Computer scientists are particularly interested in periodic schedules. Given a timed marked graph, they ask if there exist a period p > 0 and real numbers x(u) such that (G) over right arrow has a periodic schedule of the form f(u)(k) = x(u) + 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. (C) 2008 Elsevier B.V. All rights reserved.
    Relation: DISCRETE APPLIED MATHEMATICS
    Appears in Collections:[數學研究所] 期刊論文

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML578View/Open


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明