跳到主要內容

臺灣博碩士論文加值系統

(34.204.176.71) 您好!臺灣時間:2024/11/08 00:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:廖崇碩
研究生(外文):Chung-Shou Liao
論文名稱:圖的k多重支配問題
論文名稱(外文):k-Tuple Domination in Graphs
指導教授:張鎮華張鎮華引用關係
指導教授(外文):Gerard J. Chang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
中文關鍵詞:k多重支配
外文關鍵詞:k-Tuple Domination
相關次數:
  • 被引用被引用:0
  • 點閱點閱:255
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在一個圖G中, 每一個點都可以支配(dominate)它自己以及和它相鄰的點. 對一個固定的正整數k而言, k多重支配問題就是去找出最小的點集合, 使得圖G中的每個點都可以被這個點集合中至少k點支配. 這篇論文主要是從演算法的角度來研究這個問題. 我們的結果包括下面幾項; 首先, 我們提供了兩個線性時間的演算法, 分別解決了樹(trees)以及強弦圖(strongly chordal graphs)上的k多重支配問題; 此外, 我們也證明了在分裂圖(split graphs)(弦圖(chordal graphs)的子類)以及二分圖(bipartite graphs)中, k多重支配問題是NP完備的

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current thesis studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give linear-time algorithms for the k-tuple domination problem in trees and strongly chordal graphs by employing a labeling method. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and bipartite graphs.

Abstract (in Chinese)........................................i
Abstract (in English).......................................ii
Acknowledgements...........................................iii
Contents....................................................iv
List of Figures..............................................v
1. Introduction..........................................1
2. Notation and definitions..............................3
3. 2-Tuple domination in trees...........................6
4. k-Tuple domination in strongly chordal graphs........12
5. NP-Completeness results..............................18
6. Conclusion remarks...................................21
References..................................................22

[1] R. P. Anstee and M. Farber, Characterization of totally balanced matrices, J. Algo-rithms
5 (1984), 215-230.
[2] S. Arumugam and S. Velammal, Edge domination in graphs, Taiwanese J. Math. 2
(1998) 173-179.
[3] G. J. Chang, Labeling algorithms for domination problems in sun-free chordal graphs,
Discrete Applied Math. 22 (1988/89), 21-34.
[4] G. J. Chang, Algorithmic aspects of domination in graphs, in: Handbook of Combi-natorial
Optimization (D.-Z. Du and P. M. Pardalos eds.) Vol. 3 (1998) 339-405.
[5] G. J. Chang and G. L. Nemhauser, The k-domination and k-stability on sun-free
chordal graphs, SIAM J. Alg. Discrete Methods 5 (1984) 332-345.
[6] E. J. Cockayne, S. E. Goodman and S. T. Hedetniemi, A linear algorithm for the
domination number of a tree, Inform. Process. Letters 4 (1975) 41-44.
[7] M. Farber, Domination, independent domination and duality in strongly chordal
graphs, Discrete Applied Math. 7 (1984) 115-130.
[8] J. F. Fink and M. S. Jacobson, n-domination in graphs, Graph Theory with Applica-tions
to Algorithms and Computer Science, Wiley, New York (1984), 283-300.
[9] F. Harary and T. W. Haynes, Nordhaus-Gaddum inequalities for domination in
graphs, Discrete Math. 155 (1996) 99-105.
[10] F. Harary and T. W. Haynes, Double domination in graphs, Ars Combinatoria 55
(2000) 201-213.
[11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: The Theory,
Marcel Dekker, Inc. New York (1998).[12] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Selected
Topics, Marcel Dekker, Inc. New York (1998).
[13] A. J. Hoffman, A. W. J. Kolen and M. Sakarovitch, Totally-balanced and greedy
matrices, SIAM J. Alg. Discrete Methods 6 (1985) 721-730.
[14] S. F. Hwang and G. J. Chang, The edge domination problem, Discussiones Math.—
Graph Theory 15 (1995) 51-57.
[15] V. R. Kulli, On n-total domination number in graphs, in: Graph Theory, Combina-torics,
Algorithms, and Applications, SIAM Philadelphia, PA (1991) 319-324.
[16] R. Laskar, J. Pfaff, S. M. Hedetniemi and S. T. Hedetniemi, On the algorithm com-plexity
of total domination, SIAM J. Alg. Discrete Methods 5 (1984) 420-425.
[17] A. Lubiw, Doubly lexical ordering of matrices, SIAM J. Comput. 16 (1987) 854-879.
[18] S. L. Mitchell and S. T. Hedetniemi, Edge domination in trees, in: Proceedings Eighth
S. E. Conference on Combinatorics, Graph Theory and Computing, Utilitas Math.,
Winnipeg (1977) 489-509.
[19] R. Paige and R. E. Tarjan, Three partition refinement algorithms, SIAM J. Comput.
16 (1987) 973-989.
[20] P. J. Slater, R-Domination in graphs, J. Assoc. Comput. Mach. 23 (1976) 446-450.
[21] J. P. Spinrad, Doubly lexical ordering of dense 0-1 matrices, Inform. Process. Lett.
45 (1993) 229-235.
[22] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Applied
Math. 38 (1980) 364-372.
[23] H. G. Yeh and G. J. Chang, Algorithmic aspects of majority domination, Taiwanese
J. Math. 1 (1997) 343-350.
[24] H. G. Yeh and G. J. Chang, Weighted connected domination and Steiner trees in
distance-hereditary graphs, Discrete Applied Math. 87 (1998) 245-253.
[25] H. G. Yeh and G. J. Chang, Weighted k-domination and weighted k-dominating
clique in distance-hereditary graphs, Theoretical Computer Science (accepted).

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top