國立高雄大學圖資館 |

語系: 繁體中文

說明(常見問題)

圖資館首頁

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

點著色衝突問題及其自我穩定分散式演算法 = Self-stabilizi...

國立高雄大學資訊工程學系碩士班

點著色衝突問題及其自我穩定分散式演算法 = Self-stabilizing Distributed formation of Color Conflict Problem

紀錄類型:	書目-語言資料,印刷品 : 單行本
並列題名:	Self-stabilizing Distributed formation of Color Conflict Problem
作者:	蘇嘉偉,
其他團體作者:	國立高雄大學
出版地:	[高雄市]
出版者:	撰者;
出版年:	2014[民103]
面頁冊數:	54面圖，表 : 30公分;
標題:	壅塞賽局
標題:	Congestion Game
電子資源:	http://handle.ncl.edu.tw/11296/ndltd/18859716332097132363
附註:	參考書目：面52-54
附註:	104年3月25日公開
摘要註:	圖形理論(Graph theory)中的圖形著色問題(graph coloring problem)是對無向圖的頂點或邊進行著色，使得相鄰的頂點(邊)著上不同顏色，整個圖形在著色之後則盡可能地減少使用的顏色數目。圖形著色問題常被用來解決分散式系統中的資源分配(resource allocation)問題。現實中的資源常常是有限的，但要確認圖形G是否可以用k個顏色完成著色是一個NP-Complete問題。因此本論文將此問題作延伸並提出最小顏色衝突(Minimal Color Conflict; MCC)問題，除了使用固定顏色數進行著色之外，我們也允許頂點同時使用多個顏色並且希望盡量減少相鄰頂點同色產生的顏色衝突個數。為了解決此問題，我們依據了圖形壅塞賽局(graphical congestion game)設計出一個在區域集中式運算模型(locally central daemon)下的分散式自我穩定著色演算法(self-stabilizing algorithm)以及可實作於行動隨意式網路(Mobile Ad-Hoc Network; MANET)的分散式協定(distributed protocol)。 Graph coloring which is a method to use as few colors as possible for painting the vertices (or edges) of a given graph and making sure there is no two adjacent vertices share the same color. Graph coloring can be viewed as a simplification of resource allocation problems. In reality, the resources is definitely finite in distributed systems. It is NP-complete problem to decide whether a given graph can be colored by using k colors. On the basis of graph coloring problem, this paper is concerning about the Minimal Color Conflict problem of using finite colors and allows adjacent vertices using the same color, called conflicts. This paper adopts the graphical congestion game theory to reduce the number of color conflicts, and converting it into a distributed self-stabilizing algorithm under locally central daemon. Furthermore, we adapts this algorithm into a distributed protocol which can be implemented on the Mobile Ad-Hoc Networks.

點著色衝突問題及其自我穩定分散式演算法 = Self-stabilizing Distributed formation of Color Conflict Problem
蘇, 嘉偉

點著色衝突問題及其自我穩定分散式演算法 = Self-stabilizing Distributed formation of Color Conflict Problem / 蘇嘉偉撰 - [高雄市] : 撰者, 2014[民103]. - 54面 ; 圖，表 ; 30公分.
參考書目：面52-54104年3月25日公開.
壅塞賽局Congestion Game

點著色衝突問題及其自我穩定分散式演算法 = Self-stabilizing Distributed formation of Color Conflict Problem
LDR:03128nam0a2200289 450 001 446537
005 20170214101059.0
009 446537
010 0 $b 精裝
010 0 $b 平裝
100 $a 20170214d2014 k y0chiy05 e
101 1 $a chi $d chi $d eng
102 $a tw
105 $a ak am 000yy
200 1 $a 點著色衝突問題及其自我穩定分散式演算法 $d Self-stabilizing Distributed formation of Color Conflict Problem $z eng $f 蘇嘉偉撰
210 $a [高雄市] $c 撰者 $d 2014[民103]
215 0 $a 54面 $c 圖，表 $d 30公分
300 $a 參考書目：面52-54
300 $a 104年3月25日公開
314 $a 指導教授：嚴力行
328 $a 碩士論文--國立高雄大學資訊工程學系碩士班
330 $a 圖形理論(Graph theory)中的圖形著色問題(graph coloring problem)是對無向圖的頂點或邊進行著色，使得相鄰的頂點(邊)著上不同顏色，整個圖形在著色之後則盡可能地減少使用的顏色數目。圖形著色問題常被用來解決分散式系統中的資源分配(resource allocation)問題。現實中的資源常常是有限的，但要確認圖形G是否可以用k個顏色完成著色是一個NP-Complete問題。因此本論文將此問題作延伸並提出最小顏色衝突(Minimal Color Conflict; MCC)問題，除了使用固定顏色數進行著色之外，我們也允許頂點同時使用多個顏色並且希望盡量減少相鄰頂點同色產生的顏色衝突個數。為了解決此問題，我們依據了圖形壅塞賽局(graphical congestion game)設計出一個在區域集中式運算模型(locally central daemon)下的分散式自我穩定著色演算法(self-stabilizing algorithm)以及可實作於行動隨意式網路(Mobile Ad-Hoc Network; MANET)的分散式協定(distributed protocol)。 Graph coloring which is a method to use as few colors as possible for painting the vertices (or edges) of a given graph and making sure there is no two adjacent vertices share the same color. Graph coloring can be viewed as a simplification of resource allocation problems. In reality, the resources is definitely finite in distributed systems. It is NP-complete problem to decide whether a given graph can be colored by using k colors. On the basis of graph coloring problem, this paper is concerning about the Minimal Color Conflict problem of using finite colors and allows adjacent vertices using the same color, called conflicts. This paper adopts the graphical congestion game theory to reduce the number of color conflicts, and converting it into a distributed self-stabilizing algorithm under locally central daemon. Furthermore, we adapts this algorithm into a distributed protocol which can be implemented on the Mobile Ad-Hoc Networks.
510 1 $a Self-stabilizing Distributed formation of Color Conflict Problem $z eng
610 0 $a 壅塞賽局 $a 自我穩定演算法 $a 著色問題
610 1 $a Congestion Game $a Self-stabilizing Algorithm $a Graph Coloring
681 $a 008M/0019 $b 464103 4442 $v 2007年版
700 1 $a 蘇 $b 嘉偉 $4 撰 $3 700846
712 0 2 $a 國立高雄大學 $b 資訊工程學系碩士班 $3 353878
801 0 $a tw $b NUK $c 20150310 $g CCR
856 7 $z 電子資源 $2 http $u http://handle.ncl.edu.tw/11296/ndltd/18859716332097132363