臺灣博碩士論文加值系統

支配問題在圖形演算法上是很有名的問題， k 多重支配問題 就是其延伸。這個問題要求圖上的一個點不只要被一個點給支配，而是要被 k 個點支配。

針對樹的最小權值 k 多重支配問題，，拙作給了一個線性時間的演算法。針對平面圖，也證明其屬於 NP 完備集，此外也指出該證明之技巧不只對平面圖有用，還有很多圖類也可以被應用。

In a graph $G(V,E)$, a vertex $v$ dominates a vertex $u$ if $u=v$ or there is an edge from $v$ to $u$. A dominating set of $G$ is a subset $D$ of $V$ such that every vertex in $V$ is dominated by at least one vertex in $D$. Domination problem, that is proposed by K{\"o}nig, and its variations have fruitful literature more than $300$ publications. One class of those interesting variations is the {\it multiple domination problems}, i.e., each vertex in $V$ requires to be dominated by more than one vertex in $D$. In this thesis, we study the $k$-tuple domination problem on several graph classes. We give a linear time algorithm of weighted $k$-tuple domination problem, and prove NP-completeness of $k$-tuple domination problem on some graph classes like planar graphs.

Abstract I
Acknowledgement II
1 Introduction 1
2 Preliminaries 3
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Variations of Domination Set Problem . . . . . . . . . . . . . . . . 6
2.3 k-Tuple Domination Problem . . . . . . . . . . . . . . . . . . . . . 7
3 Algorithmic Results 9
3.1 Weighted k-Tuple Domination on Tree . . . . . . . . . . . . . . . . 9
3.1.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 Results of Computational Complexity 22
4.1 Hardness of k-Tuple Domination . . . . . . . . . . . . . . . . . . . . 22
4.1.1 k-Tuple Domination on Planar Graph and Others . . . . . . 23
4.1.2 Fixed Parameterized Reduction and Its Applications . . . . 25
5 Conculsion and Future Work 29
Bibliography 30

[1] D. W. Bange, A. E. Barkauskas, P. J. Slater, E±cient dominating sets in
graphs, in: D. Ringeisen, F. S. Roberts (eds.), Applications of Discrete Math-
ematics, SIAM, Philadelphia, PA, 1988, pp. 189{199.
[2] J. Bondy, U. Murty, Graph Theory With Applications, Elsevier Science Ltd,
1976.
[3] A. BrandstÄadt, V. B. Le, J. P. Spinrad, Graph classes: a survey, Society for
Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.
[4] R. Diestel, Graph Theory, vol. 173 of Graduate Texts in Mathematics,
Springer-Verlag, Heidelberg, 2005.
[5] G. S. Domke, S. T. Hedetniemi, R. C. Laskar, G. Fricke, Relationships be-
tween integer and fractional parameters of graphs, in: Graph theory, com-
binatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), vol. 1 of Wiley-
Intersci. Publ., Wiley, New York, 1991, pp. 371{387.
[6] J. F. Fink, M. S. Jacobson, n-Domination in graphs, John Wiley & Sons,
Inc., New York, NY, USA, 1985, pp. 283{300.
[7] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA,
1979.
[8] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, vol. 57 of
Annals of Discrete Mathematics, 2nd ed., North-Holland, 2004.
[9] F. Harary, T. W. Haynes, Double domination in graphs, Ars Combin. 55
(2000) 201{213.
[10] T. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs,
Pure and Applied Mathematics, Marcel Dekker, London, UK, 1998.
[11] M. A. Henning, Restricted domination in graphs, Discrete Mathematics
254 (1-3) (2002) 175{189.
[12] R. Klasing, C. Laforest, Hardness results and approximation algorithms of
k-tuple domination in graphs, Information Processing Letters 89 (2) (2004)
75{83.
[13] C.-S. Liao, G. J. Chang, Algorithmic aspect of k-domination in graphs, Tai-
wanese J. Math. 6 (2002) 415{420, nSC89-2115-M009-037 and Lee Center.
[14] C.-S. Liao, G. J. Chang, k-tuple domination in graphs, Information Processing
Letters 87 (1) (2003) 45{50.
[15] M. Satratzemi, K. G. Margaritis, C. Tsouros, An algorithm for prescribed
multiple domination in arbitrary graphs, Computers & Mathematics with
Applications 35 (8) (1998) 109{115.
[16] M. Satratzemi, K. Tsouros, Double domination algorithms in graphs, in:
Hellenic European research on mathematics and informatics '94, Vol. 1, 2
(Athens, 1994), Hellenic Math. Soc., Athens, 1994, pp. 509{516.