臺灣博碩士論文加值系統

圖G = (V, E) 的一個有效負支配集函數(minus domination function) 是將圖G的所有點給予1，0或—1的值, 但每個點與它所有有邊 (edge) 相連的鄰居的函數值加總起來會恰好等於1。所謂的有效負支配集問題則是在一個給定的圖中找尋它是否存在一個有效負支配集函數。
在一般圖 (General graphs) 上，這個問題是 NP-complete 的問題。因此，我們將這個問題放在區塊圖 (Block graphs) 上研究。在這篇論文中，我們將利用動態規劃 (Dynamic-programming) 法來給予一個時間複雜度 (Time complexity) 為 O(D4n) 的演算法來解決區塊圖上的有效負支配集問題。

A three-valued function $f$ defined on the vertices of a graph $G
= (V, E)$, $f : V \rightarrow \{-1, 0, 1\}$, is an efficient minus
dominating function if the sum of its function values over any
closed neighborhood equals to one. That is, for every $v \in V$,
$\sum_{u \in N[v]}f(u) = 1$, where $N[v]$ consists of $v$ and all
vertices adjacent to $v$. The sum of the function values of all
vertices is called the weight of $f$. The efficient minus
domination problem is to find the efficient minus dominating
function of $G$ of minimum weight. This problem is NP-complete for
general graphs. In this paper, we present an $O(\Delta^4 n)$
algorithm to solve this problem on block graphs where $\Delta$ is
the maximum degree of $G$.

Table of Contents
Table of Contents I
List of Figures I
List of Tables II
1 Introduction 1
2 A Brief Survey 3
3 A Polynomial Time Algorithm 8
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Conclusions 20
References 21

[1] C. L. Lu, C. Y. Tang, Weighted ecient domination problem on some perfect
graphs, Discrete Applied Math., 117 (2002), pp. 163
[2] M. S. Chang, B. H. Du, Ecient minus domination on proper interval graphs,
Master thesis, Department of Computer Science and Information Engineering,
National Chung Cheng University, Taiwan, (2002).
[3] P. Y. Liu, Signed domination and ecient signed domination on cographs,
Master thesis, Department of Computer Science and Information Engineering,
National Chung Cheng University, Taiwan, (2001).
[4] P. Damaschke, Minus domination in small-degree graphs, Discrete Applied
Math., 108 (2001), pp. 53
[5] C. L. Lu, S. L. Peng, C. Y. Tang, Ecient minus and signed domination in
graphs, Lecture Notes in Computer Science, 1969 (2000), pp. 241
[6] M. S. Chang, Ecient algorithms for the domination problems on interval and
circular-arc graphs, SIAM J. Comput., 27 (1998), pp. 1671
[7] C. L. Lu, On the study of weighted ecient domination, PhD thesis, Depart-
ment of Computer Science, National Tsing Hua University, Taiwan, (1998).
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in
graphs, Marcel Dekker, New York, (1998).
[9] M. S. Chang, Weighted domination of cocomparability graphs, Discrete Appl.
Math., 80 (1997), pp.135
[10] Y. D. Liang, C. L. Lu, C. Y. Tang, Ecient domination on permutation
graphs and trapezoid graphs, Lecture Notes in Computer Science, 1276 (1997),
pp.232
[11] C. C. Yen, R. C. T. Lee, The weighted perfect domination problem and its
variants, Discrete Applied Math., 66 (1996), pp. 147
[12] D. W. Bange, A. E. Barkauskas, P. J. Slater, L. H. Host, Generalized domination
and ecient domination in graphs, Discrete Math., 159 (1996), pp. 1
[13] J. Dunbar, W.Goddar, S. T. Hedetniemi, A. McRae, M. A. Henning, The al-
gorithmic complexity of minus domination in graphs, Discrete Applied Math.,
68 (1996), pp. 73
[14] G. J. Chang, C. Pandu Rangan, S. R. Coorg, Weighted independent perfect
domination on cocomparability graphs, Discrete Applied Math., 63 (1995),
pp. 215
[15] J. H. Hattingh, M. A. Henning, P. J. Slater, The algorithmic complexity
of signed domination in graphs, Australasian Journal of Combinatorics, 12
(1995), pp. 101
[16] M. S. Chang, Y. C. Liu, Polynomial algorithm for the weighted perfect dom-
ination problems on chordal graph and split graphs, Information Processing
Letters, 48 (1993), pp. 205
[17] C. C. Yen, Algorithmic aspects of perfect domination, PhD thesis, Department
of Computer Science, National Tsing Hua University, Taiwan, (1992).
[18] M. R. Fellows, M. N. Hoover, Perfect domination, Australasian Journal of Com-
binatorics, 3 (1991), pp. 141
[19] D. W. Bange, A. E. Barkauskas, P. J. Slater, Ecient dominating sets in graphs,
Application of Discrete Math., (SIAM, Philadelphia 1988), pp. 189