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

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

Title:	圖型著色及其變形(I);Graph Coloring and Its Variations(I)
Authors:	葉鴻國
Contributors:	數學系
Keywords:	數學類
Date:	2006-07-01
Issue Date:	2010-12-06 16:20:33 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	【背景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
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	399	View/Open

社群 sharing

Loading...