混合支配集合問題之研究; The Mixed Dominating Set Problem

University of Taipei > 理學院 > 資訊科學系 > 研究計畫or研究報告 > Item 987654321/16019

請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16019

題名:	混合支配集合問題之研究;The Mixed Dominating Set Problem
作者:	陳彥宏
貢獻者:	臺北市立教育大學資訊科學系
關鍵詞:	圖論;近似演算法;可近似度集合(近似複雜度);非簡單暴力的正確演算法;NP完備;支配節點集合問題;混合支配集合問題;混合配對集合問題;PMU配置;封包過濾器放置問題
日期:	2013-10-28
上傳時間:	2017-07-31 13:51:33 (UTC+8)
摘要:	本計畫所要研究的是支配節點集合問題(Dominating Set Problem)的變形問題：混合支配集合問題 (Mixed Dominating Set Problem)及混合配對集合問題(Mixed Matching Set Problem)。支配節點集合問題是圖論(Graph Theory)中非常著名的問題。給定一個無向圖G(V,E)，一個支配節點集合D 為V 內的子集合使得V\D 內的節點至少需要與D 內的一個節點相鄰(adjacent)。支配節點集合問題為在圖G 內找到一個支配節點集合使得集合內元素個數最少。一個混合支配集合MD 為一個在VE 內的子集合使得｛(VE)\MD｝內的元素(節點及邊)至少需要與MD 內的一個節點或邊相鄰或緊鄰(incident)。混合支配集合問題為在G 內找到一個混合支配集合使得集合內元素個數最少。如果我們給定圖中的節點與邊一個權重(weighted)，權重版混合支配集合問題為找一個混合支配集合使得集合內元素的權重加總最小。混合支配集合問題可以應用在PMU 配置(Phase Measurement Units Location)及封包過濾器放置 (Packet Filter Placement)問題上。另一個混合支配集合問題的最大化(Maximum)問題為混合配對集合問題。一個混合配對集合MM 為一個VE 內的子集合使得MM 內的任何兩元素(節點及邊)彼此要獨立 (independent，不相鄰也不緊鄰)。混合配對集合問題為在圖G 內找到一個混合配對集合使得集合內元素個數最多。混合支配集合問題及混合配對集合問題都已被證明為NP-Complete。之前在一些圖論的文獻上也有找出此兩個問題的一些性質，然而演算法的結果卻是非常少的。目前只有一個2 倍的近似演算法(approximation algorithm)在混合支配集合問題上，然而相關的可近似度集合(近似複雜度)、非簡單暴力(non-trivial brute force)的正確演算法(exact algorithm)及權重版的混合支配集合問題的近似演算法並沒被提出過。在混合配對集合問題上，雖然已知混合配對集合問題最佳解內的元素個數與最小極大配對問題(Minimum Maximal Matching Problem)最佳解內的元素個數加總為圖中節點個數\|V\|，然而一個在最小極大配對問題的近似演算法並不能保證可以存在一個對應的近似演算法在混合配對集合問題中。雖然也可以將在一個圖中的混合配對集合問題轉換到最大獨立節點集合問題(Maximum Independent Set Problem)在其完全圖(total graph)上，然而最大獨立節點集合問題的近似複雜度卻是不好的。因此混合配對集合問題的可近似度集合目前仍亦是未知待解。本計畫首要目標為分析在混合支配集合及混合配對集合問題的可近似度集合。之後我們也預計去設計一個正確演算法及近似演算法來求得混合支配集合問題的最佳解及混合配對集合問題的近似解。我們也有興趣討論權重版的混合支配集合問題的可近似度集合及設計其近似演算法。
關聯:	研究期間：民10108~10207，國科會計畫編號：NSC101-2221-E133-003
顯示於類別:	[資訊科學系] 研究計畫or研究報告

文件中的檔案:

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

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

資料載入中.....