圖型著色及其變形(I); Graph Coloring and Its Variations(I)

NCU Institutional Repository > 理學院 > 數學系 > 研究計畫 > Item 987654321/43104

請使用永久網址來引用或連結此文件: 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
關聯:	財團法人國家實驗研究院科技政策研究與資訊中心
顯示於類別:	[數學系] 研究計畫

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	356	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....