二分規則網路彩虹支配數之研究

CCUR > College of Business > Department of Information Management & Graduate Institute of Information Management > project > Item 987654321/21845

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/21845

Title:	二分規則網路彩虹支配數之研究
Authors:	王福星
Contributors:	資訊管理學系（所）
Keywords:	彩虹支配二分規則網路固定參數演算法 Rainbow domination Bipartite regular networks Fixed-parameter algorithms
Date:	2010-08~2012-07
Issue Date:	2012-03-26 13:25:22 (UTC+8)
Abstract:	彩虹支配問題是由Brešar、Henning和Rall 等三人於2005年提出，其定義如下：對於一個圖形G中的每一個點，我們可以指定該點為不塗色或塗以特定k 種顏色中的某些顏色。當此點被指定為不塗色時，其鄰居點所著的顏色種類的聯集必須涵蓋指定的k 種顏色。對於G中所有點的用色總個數，我們求解其最小值，稱為彩虹支配數。彩虹支配問題被熱烈討論，並有多種有趣的衍生問題，近來，學者Brešar 等人則提出大量有關彩虹支配數之研究成果。儘管多位圖論領域的知名學者提出其相關研究結果，但是針對二分規則網路上求解彩虹支配數配數之相關文獻，據我們所知仍相當有限。本計畫將試圖在彩虹支配問題剛開始為國際學者注視時，提出一系列研究。我們的研究團隊預計先針對一些二分規則網路，包括超立方圖、蝴蝶網路、蜂巢網路以及星狀圖等等圖形，進行深入探討。在計畫的第一年，我們將先行審視評估二分規則網路本身的一些特性，預期在其中發現一些有關求解二彩虹支配問題的數學性質。實際上，我們將探討二分規則網路的彩虹支配數，與一些圖形參數，例如封裝數、支配數以及全部支配數等之間的關係，藉以來定位彩虹支配數的上、下限值。植基於計畫第一年的研究結果，我們將於計畫的第二年再擴大研究成果，期望將建立對於先前擇訂之二分規則網路上有關彩虹支配研究之重要觀點(目前文獻尚未呈現者)，以提供一些關鍵性質，這將有助於發展更精確的研究，預期將用以設計出求解此問題在一些二分規則網路上的演算法。此外，對於難以求解的二分規則網路，我們將運用固定參數演算法的一些技巧，尋求此問題的逼近演算法。
Appears in Collections:	[Department of Information Management & Graduate Institute of Information Management] project

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	539	View/Open
index.html	0Kb	HTML	577	View/Open
992221E034008MY2.pdf	2376Kb	Adobe PDF	518	View/Open

Loading...