The Paired Domination Problem on Graphs

瀏覽統計 Email 通知 RSS Feed

簡歷

基本資料

Project title

Code/計畫編號

NSC99-2221-E019-022-MY2

Translated Name/計畫中文名

各種圖類上的成對支配點問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=2215953

Year

2011

Start date/計畫起

01-08-2011

Expected Completion/計畫迄

31-07-2012

Bugetid/研究經費

488千元

ResearchField/研究領域

資訊工程--硬體工程
資訊科學--軟體

支配點問題(domination problem) 與變異支配點問題在計算機科學上，不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。例如電力系統監控、通訊網路設計以及網路資源分配。根據不同的應用需求，所產生的支配點問題也不同。給定一個圖G，一個支配點集合(dominating set) 是一個點集合 S ⊆ V(G)，使得每個不在S 中的點都與 S 相鄰。支配點問題 (domination problem) 是在 G 中找一個支配點集合使得集合的元素個數為最少。如果S 的誘導子圖 G[S] 包含一個完美匹配(perfect matching)，則我們說S 是 G 的 “成對支配點集合”。成對支配點問題(paired domination problem) 是在 G 中找一個成對支配點集合使得集合的元素個數為最少。 Haynes and Slater [13] 提出了成對支配點問題並且證明它為一個 NP-complete 問題。最近幾年，Cheng 等人 [7] 在 interval graphs 以及 circular-arc graphs 分別提出了時間複雜度為 O(m+n) 以及 O(m(m+n)) 的演算法。在本研究中，我們計畫改進他們的成果，在相同的圖類上(graph class) 提出時間複雜度為 O(n) 的演算法。同時我們也將試著在strongly chordal graph 上找出時間複雜度為 O(m+n) 的演算法。最後，根據解決以上問題所得到的知識與經驗，我們期望能在一般圖上找到多項式時間的近似演算法(polynomial-time approximation algorithm)，同時希望證明在平面圖(planar graph) 上的成對支配問題為 NP-complete，並且設計此問題在平面圖上的多項式時間的近似演算法。 The dominating problem and its variants are not only fundamental in algorithmic graph theory but also practically important in many applications such as power system monitoring, communication networks and resource allocation. Based on different criteria on applications, there are different types of dominating problems. In a graph G, a vertex subset S ⊆ V(G) is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. The domination problem is to find a dominating set of G such that the size of dominating set is minimized. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired domination problem is to find a paired-dominating set of G such that the size of paired-dominating set is minimized. Haynes and Slater [13] introduced the paired domination problem and show that the paired domination problem is NP-hard. Recently, Cheng et al. [7] designed an O(m+n)-time algorithm on interval graphs and an O(m(m+n))-time algorithm on circular-arc graphs. In this project, we plan to improve their results with time complexity O(n) for the same graph classes. Furthermore, given a strong elimination order of a strongly chordal graph, we plan to propose an O(m+n)-time algorithm to find a paired-dominating set of G such that the size of paired-dominating set is minimized. Based on the experience above, we will turn on to design a polynomial-time approximation algorithm for general graphs. Meanwhile, we will also try to prove that it is NP-complete on planar graphs and provide a polynomial-time approximation algorithm.

Keyword(s)

domination problem
graph class
induced subgraph
perfect matching
graph algorithm

DSpace CRIS

The Paired Domination Problem on Graphs

基本資料

Description