簡易檢索 / 詳目顯示

回結果列表
研究生： 林秋君
Chiou-Jiun Lin
論文名稱： 區間圖上的外連通支配集問題
Finding Outer-connected Dominating Sets in Interval Graphs
指導教授： 王有禮
Yue-Li Wang
口試委員: 劉嘉傑
Jia-Jie Liu
徐俊傑
Chiun-Chieh Hsu
學位類別： 碩士
Master
系所名稱： 管理學院 - 資訊管理系
Department of Information Management
論文出版年： 2015
畢業學年度： 103
語文別： 英文
論文頁數： 27
中文關鍵詞： 支配 、外連通支配 、切點 、部分區間圖 、區間圖
外文關鍵詞： Domination, Outer-connected domination, Cut vertex, Proper Interval Graph, Interval Graph
相關次數： 點閱：253  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  •  上一筆

    • 外連通支配集在圖Ｇ是一個集合Ｓ，使得所有不在Ｓ集合的點至少需與Ｓ集合裡的一個點相鄰，並且Ｖ\S的子圖還是要為連通。在[Computing a minimum outer-connected dominating set for the class of chordal graphs, Information Processing Letters 113 (2013) 552-561] 的論文中，Keil and Pradhan 給了一個線性時間的演算法找最小的外連通支配集在部份的區間圖上，在本篇論文中，我們改善了他們的結果，以線性時間在區間圖上找最小外連通支配集。

    An outer-connected dominating set in a graph G = (V,E) is a set S⊆V such that each vertex not in S is adjacent to at least one vertex in S and the subgraph induced by V\S is connected. In [Computing a minimum outer-connected dominating set for the class of chordal graphs, Information Processing Letters 113 (2013) 552-561], Keil and Pradhan gave a linear-time algorithm for finding a minimum outer-connected dominating set in proper interval graphs. In this thesis, we generalize their result to find a minimum outer-connected dominating set in interval graphs in linear time.

    1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Previous results 4 2.1 Preliminaries .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Interval Graphs and Proper Interval Graphs . . . . . . . . . . . . . . 4 2.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 An algorithm for Finding OCD-sets in Proper Interval Graphs . . . . . 8 2.6 Some De nitions and Related Theorems . . . . . . .. . . . . . . . . . . 9 3 Main results 11 3.1 Finding Minimum OCD-set in Interval Graphs without Chained Cut-vertices 11 3.2 The Correctness of the Algorithm . . . .. . . . . . . . . . . . . . . 12 3.3 Finding Minimum OCD-set in Interval Graphs with Chained Cut-vertices . 17 4 Concluding Remarks 18

    [1] 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.
    [2] Shun-Chieh Chang, Jia-Jie Liu, and Yue-Li Wang, The Outer-connected Domination Number of Sierpi nski-like Graphs, Theory of Computing Systems, 2015.
    [3] J. Cyman, The outer-connected domination number of a graph, The Australasian Journal of Combinatorics 38 (2007) 35-46.
    [4] T.W.Haynes, S.T.Hedetniemi, P.J.Slater, Fundamentals of Domination in Graphs, Marcel Dekker, NewYork, 1998.
    [5] R.E. Jamison and R.Laskar, Elimination orderings of chordal graphs, in: Combinatorics and Applications, Calcutta, 1982, pp.192-200.
    [6] H. Jiang and E. Shan, Outer-connected domination in graphs, Utilitas Mathematica 81 (2010) 265-274.
    [7] 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.
    [8] M. Pal, S. Mondal, D. Bera, and T.K. Pal, An optimal parallel algorithm for computing cut vertices and blocks on interval graphs, International Journal of Computer Mathematics 75 (2000) 59-70.
    [9] B.S. Panda and A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs, In: S.P. Pal and K. Sadakan (eds.) WALCOM 2014, Lecture Notes in Computer Science 8344 (2014) 151-162.
    [10] D. Pradhan, On the complexity of the minimum outer-connected dominating set problem in graph, Journal of Combinatorial Optimization, 2014.

    QR CODE