University of Taipei:Item 987654321/16019
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 2446/17084 (14%)
Visitors : 3227118      Online Users : 645
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16019


    Title: 混合支配集合問題之研究;The Mixed Dominating Set Problem
    Authors: 陳彥宏
    Contributors: 臺北市立教育大學資訊科學系
    Keywords: 圖論;近似演算法;可近似度集合(近似複雜度);非簡單暴力的正確演算法;NP完備;支配節點集合問題;混合支配集合問題;混合配對集合問題;PMU配置;封包過濾器放置問題
    Date: 2013-10-28
    Issue Date: 2017-07-31 13:51:33 (UTC+8)
    Abstract: 本計畫所要研究的是支配節點集合問題(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)上，然而最大獨立節點集合問題的近似複雜度卻是不 好的。因此混合配對集合問題的可近似度集合目前仍亦是未知待解。本計畫首要目標為分析在混合支 配集合及混合配對集合問題的可近似度集合。之後我們也預計去設計一個正確演算法及近似演算法來 求得混合支配集合問題的最佳解及混合配對集合問題的近似解。我們也有興趣討論權重版的混合支配 集合問題的可近似度集合及設計其近似演算法。
    Relation: 研究期間：民10108~10207，國科會計畫編號：NSC101-2221-E133-003
    Appears in Collections:[Department of Computer Science] Research Project

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML1835View/Open


    All items in uTaipei are protected by copyright, with all rights reserved.

    如有問題歡迎與系統管理員聯繫
    02-23113040轉2132
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback