跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.91) 您好!臺灣時間:2025/02/19 20:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林宜駿
研究生(外文):YI-CHUN LIN
論文名稱:外配對支配集問題在塊狀圖形上之研究
論文名稱(外文):Outer-paired Domination Problem in Block Graphs
指導教授:王有禮
指導教授(外文):Yue-Li Wang
口試委員:王有禮
口試委員(外文):Yue-Li Wang
口試日期:2016-05-30
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:21
中文關鍵詞:外配對支配集支配集塊狀圖形
外文關鍵詞:Outer-paired Domination setDomination setBlock graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:122
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:1
給定一個圖G,V(G)和E(G)分別為圖G的點集合及邊集合。為了簡化符號我們用V和E來取代V(G)和E(G)。圖G上的一組支配集D滿足以下條件,D⊆V對每個不在D中的點一定相鄰某些存在於D中的點。支配集問題以及此問題的變形有許多豐富的延伸研究,例如獨立支配、彩虹支配、全部支配、羅馬支配等等,可以看出 這些變形支配集問題除了本身符合支配集的性質上並再加上一些限制條件。在本研究計畫中,我們將探討一 個新的支配集變形問題稱作外配對支配集問題,問題定義如下:
在一個圖G=(V,E)上的一組外配對支配集D滿足下列條件,D ⊆ V 對每個不在D中的點一定相鄰某些存在於D 中的點,而且V\D 形成的子圖必須是完美配對。外配對支配集問題就是找出一組點數最少的外配對支配集。在本論文中,我們利用動態規劃的技巧來解決外配對支配集問題在塊狀圖形上,並提供一支時間複雜度為O(m+n)的演算法。
Let G = (V, E) be an undirected graph, where V(G) and E(G) are vertex and edge sets of G, respectively. For simplicity, we also use V and E to represent V(G) and E(G),respectively, when the context is clear. A set D is a dominating set of a graph G if every vertex in V \ D is adjacent to at least one vertex in D. The domination problem and its variants were extensively studied, e.g., independent domination, rainbow domination, total domination, roman domination, etc. We can find that all variants on the domination problem are adding some constraints on the domination set itself. In this thesis, we investigate a new variant of the domination problem called the outer-paired domination problem which is defined as follows. An outer-paired domination set (OPD-set for short) of a graph G is a dominating set D of G such that the induced subgraph of V \ D contains a perfect matching. In this thesis, we use the dynamic programming skill to solve this
problem on block graphs and propose an O(m+n) algorithm.
摘 要 I

Abstract II

誌 謝 III

Contents IV

List of Figures VI

1 Introduction 1

1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Preliminaries 4

2.1 Some related graph classes and properties . . . . . . . . . . . . . . . . . . . 4

3 Main results 7

3.1 Fnding the minimum outer-paired domination number of a graph . . . . . . 12

3.2 Calculating different case procedure . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1. Computing αv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2.2. Computing βv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.3. Computing γv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.4. Computing βv+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.5. Computing γv+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3. Merge blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Concluding Remarks 19

4.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

References 20
[1] R.B. Allan and R.C. Laskar, On domination and independent domination numbers

of a graph, Discrete Mathematics 23 (1978) 73–76.

[2] M.H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami, On the

outer-connected domination in graphs, Journal of Combinatorial Optimization 26

(2013) 10–18.

[3] John Adrian Bondy and U.S.R. Murty, Graph Theory with Applications, 1977

[4] B. Bre˘sar and T.K.

˘

Sumenjak, On the 2–rainbow domination in graphs, Discrete

Applied Mathematics 155 (2007) 2394–2400.

[5] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi, and S.T. Hedetniemi, On Roman

domination in graphs, Discrete Mathematics 278 (2004) 11–22.

[6] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Net-

works 10 (1980) 211–219.

[7] J. Cyman, The outer-connected domination number of a graph, The Australasian

Journal of Combinatorics 38 (2007) 35–46.

[8] J.F. Fink and M.S. Jacobson, n-domination in graphs, Graph Theory with Applica-

tions to Algorithms and Computer Science, John Wiley and Sons, New York (1985),

282–300.

[9] H. Jiang and E. Shan, Outer-connected domination in graphs, Utilitas Mathematica

81 (2010) 265–274.

[10] J.M. Keil and D. Pradhan, Computing a minimum outer-connected dominating set

for the class of chordal graphs, Information Processing Letters 113 (2013) 552–561.

[11] Chih Yuan Lin, Jia Jie Liu, Yue Li Wang and Chiun Chieh Hsu, Dominating Sets with

Matching Outside, The 32nd Workshop on Combinatorial Mathematics and Compu-

tation Theory(2015) 71–76.

[12] Ching-Chi Lin and Cheng-Yu Hsieh, Linear-Time Algorithm for the Paired-

Domination Problem on Weighted Block Graphs, The 32nd Workshop on Combi-

natorial Mathematics and Computation Theory

[13] D.B. West, Introduction to Graph Theory.(2nd ed.), River, N.J.: Prentice-Hall, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top