Abstract
在一個簡單圖 (simple graph) G = (V, E) 裡，一個點 (vertex) 可以 支配 (dominate) 自己以及其它與之相鄰的點。所謂的有效支配集 (efficient dominating set) 是指一個點的子集合 D 使得圖 G 中的每 一個點只能被 D 中唯一的某個點給支配。有效支配問題就是在圖 G 中找 一個點的個數是最小的有效支配集。假若每個點上皆有一個實數加權值， 那麼所謂的加權有效支配問題即在 G 中找一個有效支配集使得其點的加 權值的和越小越好。有效支配的研究在許多不同的電腦科學領域上，譬如 編碼理論、圖的嵌入、地理位置上設備的配置以及在平行系統上資源的配 置等等，皆有許多的應用。有效支配在一些圖上，包括 bipartite 圖、 chordal 圖和點分支 (degree) 不超過 3 的 planar 圖等，已被證明是 NP-complete 的問題（即不容易解的問題）。但其加權有效支配問題在許 多特殊圖上，如 trees、 series-parallel 圖、split 圖、block 圖、 interval 圖、cocomparability 圖和 circular-arc 圖，卻可以在多項 式時間 (polynomial time) 甚至線性時間 (linear time) 內被找出解來 。在這本論文集內，我們證明了在 planar bipartite 圖、planar bipartite 的線圖 (line graphs) 和 chordal bipartite 圖上，有效支 配是NP-complete 的問題。同時，對加權有效支配問題，我們在 bipartite permutation 圖、permutation 圖、trapezoid 圖和 distance-hereditary 圖分別設計出計算時間為 O(|V|)、O(|V|+|E'|)、 O(|V|loglog|V|+|E'|) 和 O(|V|) 的演算法。註：|E'| 表示在 G 的互 補圖 (complement) 中所有邊 (edges) 的個數。另一方面，我們也在一 些特殊圖上對有效邊支配問題 (efficient edge domination problem) 做些探討與研究。該問題在一般的圖 (general graphs) 上已被證明是 NP-complete 的，但在 generalized series-parallel 圖和 interval 圖上是線性時間內可解的。至於其加權的有效邊支配問題，並沒有太多的 著作被發表。在這本論文集裡，我們證明了在 planar bipartite 圖上， 有效邊支配是 NP-complete 的問題，因此在 planar 圖和 bipartite 圖 上，該問題也是 NP-compelte。除此之外，對加權有效邊支配問題，我們 分別在 generalized series-parallel 圖和 chordal 圖上設計出計算時 間為 O(|V|+|E|) 的演算法。值得一提的是，在 chordal 圖上，加權有 效支配是 NP-complete 的問題，但加權有效邊支配卻是線性時間內可解 的問題。 Given a simple graph G=(V, E), a vertex v \in V is said to dominate itself and all vertices u in V which are adjacent to v. A subset D of V is called an efficient dominating set of G if every vertex in V is dominated by exactly one vertex in D. The efficient domination problem is to find an efficient dominating set of G with the minimum cardinality. Suppose that each vertex v in V is associated with a real number. Then, the weighted efficient domination problem is to find an efficient dominating set with the minimum weight in G. There are many interesting applications for efficient domination in coding theory, graph embedding, facility location on geographical area and resource allocation in parallel processing system. It is well known that the efficient domination problem is NP-complete for bipartite graphs, chordal graphs and planar graphs of maximum degree three. Much research has been devoted to investigating the algorithmic complexity of the weighted efficientdomination problem on other special classes of graphs, such as trees, series-parallel graphs, split graphs, block graphs, interval graphs, cocomparability graphs and circular-arc graphs. In this dissertation, we show that the efficient domination problem is NP-complete when restricted to planar bipartite graphs, the line graphs of planar bipartite graphs and chordal bipartite graphs. For the weighted efficient domination problem, we present an O( |V|) time algorithm on bipartite permutation graphs,an O(|V|+|E' |) time algorithm on permutation graphs, an O(|V|loglog|V|+|E'|) time algorithm on trapezoid graphs and an O(|V|) time algorithm on distance-hereditary graphs,where |E'| denotes the number of edges in the complement of G.On the other hand, we also investigate the algorithmic complexity of the edge version problem of efficient domination in graphs. The efficient edge domination problem on general graphs has been shown to be NP- complete, but can be solved in linear time when restricted to generalized series-parallel graphs and interval graphs. As to the weighted version of this problem, few work has been published. In this dissertation, we prove that the efficient edge domination problem is NP-complete when restricted to planar bipartite graphs and hence it remains NP-complete on any superclass of planar bipartite graphs, e.g., planar graphs and bipartite graphs. In addition, we present O(|V|+|E|) time algorithms to solve the weighted efficient edge domination problem on bipartite permutation graphs, generalized series- parallel graphs and chordal graphs. It is worth mentioning that on chordal graphs, the weighted efficient domination problem is NP-complete, but the weighted efficient edge domination is linear time solvable.