# 臺灣博碩士論文加值系統

(44.220.181.180) 您好！臺灣時間：2024/09/14 11:07

:::

### 詳目顯示

:

• 被引用:0
• 點閱:271
• 評分:
• 下載:3
• 書目收藏:0
 令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摘要 iAbstract iiTable of contents iiiList of figures ivList of tables vi1 Introduction 12 A Survey on Cographs 53 Background Results and Basic Terminology 174 The Maximum Restricted Paired Domination Problem onCographs 205 Concluding Remarks 41List of Figures1 A graph G with restricted vertex set R = {b; c}, where restricted vertices are drawn by filled circles. 62 (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. . . . . . . . . . . . . . . . . . . . . . . . . . 73 The containment relations among the considered graph classes. . . . . . . . . . . . . . . . . . . . . . 154 The partitions of VL and VR. . . . . . . . . . . . . 275 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 filledcircles, symbol ‘×’ denotes the destruction to one pair inMRPDL, and arrow lines represent the new pairs for the construction. . . . . . . . . . . . . . . 296 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. . . . . 337 (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. . . . . . . . . . . . . . . . . . . 40List of Tables1 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 dominationproblems 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 學習成就與電玩涉入對國小高年級學童人際關係影響之研究 2 一個有效率的行動代理人有限期的階層式金鑰管理機制 3 利用改良式差分進化及文化演算法於遞迴式函數類神經模糊網路之設計與應用 4 一個以後門赫序函數運算之高效率電子現金系統 5 適用於車載網路上具通訊暨換手管理的安全協定 6 具高效率之電子郵件方案與交談金鑰協定 7 機構投資者持股類型、公司治理與策略性資產減損認列之關係 8 以台灣對美、日之貿易指標探討台灣產業結構變化 9 兩岸保險法制之比較-以產物保險為核心探討 10 銀行業經營銀行保險之策略分析 11 雙起賠保單應用在證券交易風險管理之研究 12 應用K.K.音標教學與折衷式教學觀，結合同儕教導模式提升高職生英語學習能力之研究－以中部某一私立高職為例 13 產品服務系統的環境與經濟效益之研究 14 中部空品區國道移動污染源對臨近居民健康影響之研究 15 中國式領導行為、組織公平與組織信任關係之研究－以某科技研發機構為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室