| 題名: | 支配著色問題之研究;The Dominated Coloring Problem |
| 作者: | 陳彥宏 |
| 貢獻者: | 臺北市立大學資訊科學系 |
| 關鍵詞: | 圖論;計算複雜度;近似複雜度(可近似度集合);近似演算法;非簡單暴力的正確演算法;NP完備;支配集合問題;著色問題;支配著色問題;支配者著色問題;特殊圖;二分圖(bipartite graphs);弦圖(chordal graphs);分離圖(split graphs);區間圖(interval graphs);社交網路中開拓人際關係;設備配置 |
| 日期: | 2014 |
| 上傳時間: | 2017-07-31 13:51:30 (UTC+8) |
| 摘要: | 本計畫所要研究的是支配集合問題(Dominating Set Problem)及著色問題(Graph Coloring)的雙準則網路設計問題(Bicriteria Network Design Problem)：支配著色問題(Dominated Coloring Problem)及支配者著色問題(Dominator Coloring Problem)。支配集合及著色問題是圖論(Graph Theory)中非常著名的問題。給定一個無向圖G(V,E)，兩個節點稱為相鄰(adjacent)如果圖上有一個邊連結此兩節點。圖上的某些節點集合S被某個節點v所支配(dominated)則是定義為v與S\{v}內的所有節點都相鄰，也可以說v為支配者(dominator)(或支配節點)支配(dominates)集合S。一個支配集合(Dominating Set)D為V內的子集合使得V\D內的節點至少需要與D內的一個節點相鄰。著色(Graph Coloring)則是在圖G的所有節點塗上顏色使得任兩個相鄰節點要塗不同顏色。支配著色(Dominated Coloring)則是結合此兩個條件(bicriteria)必須要在圖上著色並滿足在圖上每個相同顏色的節點要被圖上某個節點所支配(要與圖上某個節點相鄰)。支配著色問題(Dominated Coloring Problem)為在圖G內找到一個支配著色使得不同顏色的個數要最少。支配者著色(Dominator Coloring)則是必須要在圖上著色並滿足在圖上每個節點需要支配至少一個相同顏色的所有節點。支配者著色問題(Dominator Coloring Problem)為在圖G內找到一個支配者著色使得不同顏色的個數要最少。這兩個問題可以應用在社交網路(Social Network)中開拓人際關係(Developing Interpersonal Relationships)及設備配置(Facility Location)上。支配者著色問題已被證明為NP-Complete，在二分圖(bipartite graphs)、平面圖(planar graphs)、分離圖(split graphs)下。之前在一些圖論的文獻上在討論支配者著色問題大多是在找出最佳解的值會bound在多少之間在一般圖及一些特殊圖時，然而演算法及計算複雜度的結果卻是非常少的。目前只有一個 倍的近似演算法(approximation algorithm)在支配者著色問題上，然而相關的近似複雜度(可近似度集合)、非簡單暴力(non-trivial brute force)的正確演算法(exact algorithm)在一般圖及特殊圖下目前尚未被提出過。支配著色問題也是NP-Complete。然而目前的結果只有一篇文獻，所列的結果也是偏向在找出支配著色問題的最佳解的值會bound在多少之間在一般圖及一些特殊圖時。相關的正確演算法、計算複雜度、近似演算法在一般圖及一些特殊圖下目前亦仍是未知待解的問題。本計畫目標為設計第一個或更好的近似演算法或正確演算法來求得支配著色問題或支配者著色問題的近似解或正確解在一般圖或一些特殊圖下，例如：二分圖(bipartite graphs)、弦圖(chordal graphs)、分離圖(split graphs)、區間圖(interval graphs)等，且分析計算複雜度或近似複雜度(可近似度集合)。 |
| 關聯: | 研究期間：民10308~10407，國科會計畫編號：MOST103-2221-E845-001 |
| 顯示於類別: | [資訊科學系] 研究計畫or研究報告
|
如有問題歡迎與系統管理員聯繫 
