臺灣博碩士論文加值系統

令G = (V;E) 為一個不含孤立點的圖形。給定一個集合S ⊆ V，如果所有V − S中的頂點，都跟S有邊相鄰且S在G中的延生子圖(induced subgraph)，會包含一個完美配對(perfect matching)M，則稱S為配對駕馭集(paired-dominating set)。配對駕馭的問題在於找出圖形中含有最小基數(minimum cardinality)的配對駕馭集。
令R 為圖形G中的頂點子集且PD為G中任一配對駕馭集。若e = (u; v) ∈ M，則稱u和v為M中的一組配對(pair)。如果一個在M中的配對，其配對的兩個頂點皆不在R中，則稱做自由對(free-pair)。一個圖形G中，相對於R的最大限制的配對駕馭集(maximum restricted paired-dominating set)MRPD 是G的一個配對駕馭集，滿足|MRPD ∩ R| > |PD ∩ R|。最大限制配對駕馭集的問題在於找出圖形中最大限制的配對駕馭集且其內擁有最少的自由對。若R為一個空集合，則此問題等同於傳統的配對
駕馭的問題。本論文，我們提出一個線性時間的演算法來解決補圖(cographs)上最大限制的配對集駕馭集問題。

Let G = (V;E) be a graph without isolated vertices. A set S ⊆ V is a paired-dominating set if every vertex in V − S is adjacent to a vertex in S and the subgraph G[S] induced by S contains a perfect matching M. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality.
Let R be a subset of vertices ofG, PDbe any paired-dominating set of G, and let M be a perfect matching M of G[PD]. If e = (u, v) ∈ M, we say that u and v form a pair in M. A pair in a matching M is called free-pair if neither of its both vertices is inR. A maximum restricted paired-dominating set of G with respect to R is a paired-dominating set MRPD such that |MRPD ∩ R| > |PD ∩ R|. The maximum restricted paired-domination problem is to find a maximum restricted paired-dominating set of G w.r.t R with the least number of free-pairs. If R is empty, the stated problem coincides with the classical paired-domination problem. In this thesis, we present a linear-time algorithm to solve the maximum restricted paired-domination problem in cographs.

Contents
摘要 i
Abstract ii
Table of contents iii
List of figures iv
List of tables vi
1 Introduction 1
2 A Survey on Cographs 5
3 Background Results and Basic Terminology 17
4 The Maximum Restricted Paired Domination Problem on
Cographs 20
5 Concluding Remarks 41
List of Figures
1 A graph G with restricted vertex set R = {b; c}, where restricted vertices are drawn by filled circles. 6
2 (a) A cograph G with restricted vertex set R = {a, f, i}, and (b) a decomposition tree DT(G) of G, where restricted vertices are drawn by filled circles. . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 The containment relations among the considered graph classes. . . . . . . . . . . . . . . . . . . . . . 15
4 The partitions of VL and VR. . . . . . . . . . . . . 27
5 The construction of a restricted paired-dominating set MRPD of G for (a) Case 2.1, and (b)–(d) Case 2.2, where restricted vertices are drawn by filled
circles, symbol ‘×’ denotes the destruction to one pair inMRPDL, and arrow lines represent the new pairs for the construction. . . . . . . . . . . . . . . 29
6 The construction of a restricted paired-dominating setMRPD of G for Case 2.3, where (a) the partition of VL and VR for the case, (b) the construction of a paired-dominating set for case of {L ̸= 0, and (c)–(e) the construction of a paired-dominating set for case of {L = 0. Note that restricted vertices are drawn by filled circles, symbol ‘×’ denotes the destruction to one pair in MRPDL, and arrow lines represent the new pairs for the construction. . . . . 33
7 (a) The construction of a restricted paired-dominating set MRPD of G for case of {L > etaR +fR , and (b) the pairs in a maximum restricted paired-dominating set MPD of G with the largest number of mixed pairs, where restricted vertices are drawn by filled circles and arrow lines represent the new pairs for the construction. . . . . . . . . . . . . . . . . . . 40
List of Tables
1 The complexity results for the cograph problems . . 16

[1] G.S. Adhar and S. Peng, Parallel algorithms for cographs and parity graphs with applications, J. Algorithms 11 (1990) 252- 284.
[2] H.J. Bandelt and H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986) 182-208.
[3] H.L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Inform. Process. Lett. 31 (1989) 135-138.
[4] B.L. Bodlaender and R.H. Mohring, The pathwidth and treewidth of cographs, SIAM J. Discrete Math. 6 (1993) 181- 188.
[5] H.L. Bodlaender and T. Wolle, Contraction degeneracy on cographs, Department of Information and Computing Sciences, University of Utrecht, 2004.
[6] A. Bretscher, D. Corneil, M. Habib and C. Paul, A simple linear time LexBFS cograph recognition algorithm, Lecture Notes in Comput. Sci., vol. 2880, Springer, 2003, pp. 119-130.
[7] G.J. Chang, L.H. Huang, and H.G. Yeh, On the rank of a cograph, Linear Algebra Appl. 429 (2008) 601-605.
[8] M.S. Chang, S.Y. Hsieh, and G.H. Chen, Dynamic programming on distance-hereditary graphs, Lecture Notes in Comput. Sci., vol. 1350, Springer, 1997, pp. 344-353.
[9] T.C.E. Cheng, L. Kang, and C.T. Ng, Paired domination on interval and circular-arc graphs, Discrete Appl. Math. 155 (2007) 2077-2086.
[10] T.C.E. Cheng, L. Kang, and E. Shan, A polynomial-time algorithm for the paired-domination problem on permutation graphs, Discrete Appl. Math. 157 (2009) 262-271.
[11] L. Chen, C. Lu, and Z. Zeng, Labelling algorithms for paired domination
problems in block and interval graphs, to appear in: J. Comb. Optim., 2008.
[12] D.G. Corneil, H. Lerchs, and L.K. Stewart, Complement reducible graphs, Discrete Appl. Math. 3 (1981) 163-174.
[13] D.G. Corneil, Y. Perl, and L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985) 926-934.
[14] G. Damiand, M. Habib, and C. Paul, A simple paradigm for graph recognition: application to cographs and distance hereditary graphs, Theoret. Comput. Sci. 263 (2001) 99-111.
[15] M. Demange, T. Ekim and D. de Werra, Partitioning cographs into cliques and stable sets, Discrete Optimization 2 (2005) 145-153.
[16] R. de Souza Francisco, S. Klein and L.T. Nogueira, Characterizing
(k, l)-partitionable Cographs, Electronic Notes in Discrete Math. 22 (2005) 277-280.
[17] T. Ekim, N.V.R Mahadev and D. de Werra, Polar cographs, Discrete Appl. Math. 156 (2008) 1652-1660.
[18] M. Habib and C. Paul, A simple linear time recognition for cograph recognition, Discrete Appl. Math. 145 (2005) 183-197.
[19] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[20] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[21] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206.
[22] S.T. Hedetniemi and R.C. Laskar, Eds., Topics on domination in graphs, Discrete Math. 86 (1990).
[23] S.Y. Hsieh, A faster parallel connectivity algorithm on cographs, Appl. Math. Lett. 20 (2007) 341-344.
[24] R.W. Hung, A linear-time algorithm for the terminal path cover problem in cographs, The Journal of Chaoyang University of Technology 13 (2008) 487-518.
[25] D.G. Kirkpatrick, K.Madhukar Reddy, C.Pandu Rangan, and A. Srinivasan, Partial and perfect path covers of cographs, Discrete Appl. Math. 89 (1998) 143-153.
[26] F. Larrion, C.P. de Mello, A. Morgana, V. Neumann-Lara, and M.A. Piza~na, The clique operator on cographs and serial graphs, Discrete Math. 282 (2004) 183-191.
[27] H. Lerchs, On cliques and kernels, Department of Computer Science, University of Toronto, 1971.
[28] D. Lokshtanov, F. Mancini and C. Papadopoulos, Characterizing and computing minimal cograph completions, to appear in: Discrete Appl. Math., 2009.
[29] K. Nakano, S. Olariu, and A.Y. Zomaya, A time-optimal solution for the path cover problem on cographs, Theoret. Comput. Sci. 290 (2003) 1541-1556.
[30] S.D. Nikolopoulos and L. Palios, Recognizing cographs and threshold graphs through a classification of their edges, Inform. Process. Lett. 74 (2000) 129-139.
[31] S.D Nikolopoulos and C. Papadopoulos, Counting Spanning Trees in Cographs, Electronic Notes in Discrete Math. 13 (2003) 84-92.
[32] S.D. Nikolopoulos and L. Palios, Efficient parallel recognition of cographs, Discrete Appl. Math. 150 (2005) 182-215.
[33] V. Prakash, An efficient g-centroid location algorithm for cographs, International Journal of Mathematics and Mathematical Sciences 9 (2005) 1405-1413.
[34] H. Qiao, L. Kang, M. Cardei, and D.Z. Du, Paired-domination of trees, J. Global Optim. 25 (2003) 43-54.
[35] C. Retore, Handsome proof-nets: perfect matchings and cographs, Theoret. Comput. Sci. 294 (2003) 473-488.
[36] G.F Royle, The rank of a cograph, The electronic journal of combinatorics, 10 (2003) N11. (http://www.emis.de/journals/EJC/Volume 10/PDF/v10i1n11.pdf)
[37] R. Shamir and R. Sharan, A fully dynamic algorithm for modular decomposition and recognition of cographs, Discrete Appl. Math. 136 (2004) 329-340.
[38] G. Steiner, On the k-path partition problem in cographs, Congr. Numer. 147 (2000) 89-96.
[39] W.C.K. Yen and C.Y. Tang, The searchlight guarding problem on weighted split graphs and weighted cographs, Networks 35 (2000) 195-206.
[40] M.S. Yu and C.H. Yang, An O(n) time algorithm for maximum matching on cographs, Inform. Process. Lett. 47 (1993) 89-93.