English
| 正體中文 |
简体中文
|
全文筆數/總筆數 : 80990/80990 (100%)
造訪人次 : 42696701 線上人數 : 1429
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by
NTU Library IR team.
搜尋範圍
全部NCUIR
理學院
數學系
--研究計畫
查詢小技巧:
您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
進階搜尋
主頁
‧
登入
‧
上傳
‧
說明
‧
關於NCUIR
‧
管理
NCU Institutional Repository
>
理學院
>
數學系
>
研究計畫
>
Item 987654321/43104
資料載入中.....
書目資料匯出
Endnote RIS 格式資料匯出
Bibtex 格式資料匯出
引文資訊
資料載入中.....
資料載入中.....
請使用永久網址來引用或連結此文件:
http://ir.lib.ncu.edu.tw/handle/987654321/43104
題名:
圖型著色及其變形(I)
;
Graph Coloring and Its Variations(I)
作者:
葉鴻國
貢獻者:
數學系
關鍵詞:
數學類
日期:
2006-07-01
上傳時間:
2010-12-06 16:20:32 (UTC+8)
出版者:
行政院國家科學委員會
摘要:
【背景1】下面這篇與朱緒鼎教授合作的論文中,「Resource-sharing system scheduling and circular chromatic number」 to appear in Theoretical Computer Science ( SCI ), (己接受、預計2005年印行), 共19頁. 我們指出γ*(G) 恰好是circular chromatic number χc(G)的倒數。並把scheduling與coloring 透過acyclic orientation給聯繫起來。【背景2】在下面這篇初步完成的論文中我們探討了scheduling、coloring及 離散事件動態系統 (Discrete Event Dynamic System)之間的關係,Title: A Dynamic View of Circular Colorings, Author: H.G Yeh (preprint, 共16頁, 2004年10月)。我們將delay的概念引進scheduling 中來討論,我們發現它在edge-weighted directed graph 的circular chromatic number中的對應物為 edge weight。 此一聯繫是透過 Reiter在 Karp-Miller computation graphs 上前瞻性的工作來証明的。而且我們發現這聯繫「乾淨」且自然。最後我們透過「動態」(dynamic)的角度與技巧來對circular chromatic number導出全新且比以往更好的下界。【目的】在背景1、2這.篇論文中我們已經在circular coloring與離散事件動態系統及scheduling之間建立了初步的聯繫。而這聯繫更導引出下面這些急待解決的問題與嘗試的方向,本研究計劃預期在3年期執行完畢後,將下面可能的方向都嘗試過,且解決大半下麵條列的問題。『1』 目前我們發現scheduling by edge reversal與Markov chains 有密切的關係,我們計劃在scheduling by edge reversal 中找出類似馬可夫鏈中的transition matrix,再用處理Markov chains的技巧(例如 ergodic theorem 等)來解決scheduling by edge reversal裡面的問題。『2』 在背景2這篇論文中我們用純組合的手法在對circular chromatic number用edge reversal的看法後得到相當深刻的下界。在証明的過程中我們發現若能對圖的結構與independent sets的vertex boundary (or edge boundary)有更良好的控制,則我們會得到更好的下界。在本計劃中我們希望透過對Szemeredi's Regularity Lemma的瞭解來控制圖的結構,再透過對 Discrete Isoperimetric Inequalities 等帶有拓樸味道的工具的瞭解來控制independent sets的vertex boundary (or edge boundary)。『3』 目前我們也發現scheduling by edge reversal與min-plus algebra中的eigenvalue有密切的關係,我們計劃在min-plus algebra中找出能瞭解eigenvalue行為的方法。我們想要知道在min-plus algebra中是否有類似線性代數中的Gersgorin disc theorem. 等。『4』 在本計劃中徹底的把scheduling by edge reversal與parallel chip firing的關係做一番整理與研究並旁及Sandpiles。 研究期間:9408 ~ 9507
關聯:
財團法人國家實驗研究院科技政策研究與資訊中心
顯示於類別:
[Department of Mathematics] Research Project
文件中的檔案:
檔案
描述
大小
格式
瀏覽次數
index.html
0Kb
HTML
347
檢視/開啟
在NCUIR中所有的資料項目都受到原著作權保護.
社群 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 ©
-
隱私權政策聲明