計算梯形圖內頂點覆蓋的個數

Counting the Number of Vertex Covers in a Trapezoid Graph

陳永瑞(Yung-Jui Chen)

指導教授 ： 林敏勝

國立臺北科技大學/電資學院/電機工程系所/博士(2009年)

https://doi.org/10.6841/NTUT.2009.00089

摘要

一個圖形G = (V, E)的頂點覆蓋是指一個頂點集合V的子集合，使得每個包含於邊集合E內的邊(u, v)，頂點u和v至少有一個是落在頂點覆蓋內。一個頂點覆蓋所包含的頂點個數稱之為其頂點數(或基數)，一個頂點覆蓋C稱為極小頂點覆蓋若且唯若沒有任何頂點覆蓋C的真子集合是頂點覆蓋，而一個具有最小頂點數的頂點覆蓋稱之為最小頂點覆蓋，一個具有最大頂點數的極小頂點覆蓋稱之為最大的極小頂點覆蓋。頂點覆蓋問題為著名NP-complete問題中的一個，根據計算複雜度理論，清楚知道有關頂點覆蓋跟它變形的計數問題為#P-complete。因此，本論文著墨在#P-complete問題的限制子類別上。首先呈現本論文就梯形圖而言的貢獻為對於計數其(1)頂點覆蓋的個數、(2)極小頂點覆蓋的個數、(3)最小頂點覆蓋的個數和(4)最大的極小頂點覆蓋的個數有個別的O(n^2)演算法。其次，提出一個對於權重梯形圖，可同時求出其(1)具有最小權重的極小頂點覆蓋的個數和(2)具有最大權重的極小頂點覆蓋的個數之O(n^2)演算法。最後，對於區間圖，個別提出對於計算其(1)最小頂點覆蓋的個數和(2)最大的極小頂點覆蓋的個數之O(n)演算法。

關鍵字

(極小的、最小的、最大極小的)頂點覆蓋 ； (權重)梯形圖 ； 區間圖 ； 組合問題 ； 計數問題

並列摘要

A vertex cover C of a graph G = (V, E) is a subset of vertices V such that for every edge (u, v) ⊆ E, at least one of the vertices u or v is in the vertex cover. The number of vertices that a vertex cover contains is referred to as its size (or cardinality). A vertex cover C is called a minimal vertex cover if and only if no proper subset of C is a vertex cover. A vertex cover with minimum size is called a minimum vertex cover. A minimal vertex cover with maximum size is called a maximum minimal vertex cover. The VERTEX COVER problem is one of the well known NP-complete problems. By the theory of computing complexity, clearly, the computing problems for vertex covers and variants are #P-complete. Hence, this study works on restricted sub-classes of #P-complete problems. The contributions of the dissertation for a trapezoid graph presented firstly herein are O(n^2) algorithms for counting the number of (1) vertex covers, (2) minimal vertex covers, (3) minimum vertex covers and (4) maximum minimal vertex covers, respectively. Next, it presents an O(n^2) algorithm for counting the number of (1) minimum weighted minimal vertex covers and (2) maximum weighted minimal vertex covers simultaneously in a weighted trapezoid graph. Finally, for an interval graph, it proposes O(n) algorithms for counting the number of (1) minimum vertex covers and (2) maximum minimal vertex covers, respectively.

並列關鍵字

(Minimal, Minimum, Maximum minimal) vertex cover ； (Weighted) Trapezoid graph ； Interval graph ； Combinatorial problems ； Counting problem

參考文獻

34. M. J. Jou and J. J. Lin, "The Number of Minimal Vertex Covers in the Product of Stars or Paths", Ling Tung Journal, vol. 23, 2008, pp. 11-20.

3. Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, New York, Academic Press, 1980.

Journal Papers

6. M. I. AbouelhodaE, E. Ohlebusch, "Chaining algorithms for multiple genome comparison", Journal of Discrete Algorithms, vol. 3, no. 2-4, 2005, pp. 321-341.

7. D. Bera, M. Pal and T.K. Pal, "An efficient algorithm to generate all maximal cliques on trapezoid graphs", Int. J. Comput. Math. vol 79, no. 10, 2002, pp. 1057-1065.