Paired-Domination Problem in Weighted Circular-Arc Graphs and Related Problems

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

MOST103-2221-E019-034

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=8352083

Year

2014

Start date/計畫起

01-08-2014

Expected Completion/計畫迄

31-07-2015

Bugetid/研究經費

612千元

ResearchField/研究領域

資訊工程--硬體工程

對於一個點集合 S ⊆ V(G)，如果每個不在 S 中的點都與 S 相鄰，則我們稱 S 是一個支配點集合 (dominating set)。對於一個支配點問題 (domination problem)，我們希望在 G 中找一個支配點集合使得集合的元素個數為最少。如果 S 的誘導子圖 G[S] 包含一個完美匹配 (perfect matching)，則我們稱 S 是 G 的 “成對支配點集合”。對於一個成對支配點問題 (paired domination problem) 我們希望在 G 中找一個成對支配點集合使得集合的元素個數為最少。我們已經在 99 年國科會計畫中 [14] 對成對支配點問題 (the paired domination problem) 做深入的研究與探討，並且在圓弧圖 (circular-arc graphs) 上得到一個線性時間 (O(n)) 演算法。這個研究成果目前已經投稿到 Theoretical Computer Science [18]。延續之前的研究成果，我們將更深入探討在加權圖上的成對支配點問題。加權圖上的成對支配點問題不僅在理論研究上有趣，同時也具有許多實務上的應用。例如電力系統監控、通訊網路設計以及網路資源分配。 Haynes and Slater [13] 首先提出了成對支配點問題並且證明它為 NP-complete 問題。最近幾年，Cheng 等人 [7] 在 interval graphs 以及 circular-arc graphs 分別提出了時間複雜度為 O(m+n) 以及 O(m(m+n)) 的演算法。我們在 99 年國科會計畫中，改進 Cheng 等人的成果。在相同的圖類上 (graph class) 提出時間複雜度為 O(n) 的演算法。在本研究中，我們計畫延續之前的研究成果，在加權的區間圖、圓弧圖和區塊圖，都提出線性時間的演算法。最後，根據解決以上問題所得到的知識與經驗，我們試著能在一般圖 (general graph) 上找到多項式時間的近似演算法 (polynomial-time approximation algorithm)，同時希望證明在平面圖 (planar graph) 上的成對支配問題為 NP-complete，並且設計此問題在平面圖上的多項式時間的近似演算法。 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. 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 involves finding a smallest paired-dominating set of G. In the previous NSC project [15], we have studied the paired-domination prob- lem and proposed an algorithm for circular-arc graphs that runs in O(n) time. The results have been submitted to Theoretical Computer Science [13]. Based on the work we have done in the previous NSC project, we further investigate the paired-domination problem on weighted graphs. 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. Haynes and Slater [14] defined the paired-domination problem and showed that it is NP-complete in general graphs. More recently, Cheng et al. [23] designed an O(n+m)-time algorithm for interval graphs and an O(m(n+m))-time algorithm for circular-arc graphs. In the previous NSC project, we improve the above results with time complexity O(n) for interval graphs and circular-arc graphs. In this project, we plan to extend the results to design O(n + m)-time algorithms for weighted interval graphs, circular-arc graphs and block graphs. Based on the experience above, we will turn on to design an O(n + m)-time algorithm for block graphs and 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
weighted graph
induced subgraph
perfect matching
graph algorithm

DSpace CRIS

Paired-Domination Problem in Weighted Circular-Arc Graphs and Related Problems

Details

Description