目標集選擇問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.147.49.185

姓名

江俊瑩(Chun-ying Chiang) 查詢紙本館藏

畢業系所

數學系

論文名稱

目標集選擇問題
(On the target set selection problem)

相關論文

★ 圓環面網路上的病毒散播	★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs	★ On the Steiner medians of a block graph
★ 圖形列表著色	★ 秩為5的圖形
★ Some results on distance-two labeling of a graph	★ 關於非奇異線圖的樹
★ On Minimum Strictly Fundamental Cycle Basis	★ 路徑圖與格子圖上的目標集問題
★ 超立方體圖與格子圖上的目標集問題	★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較	★ 數樹：方法綜述
★ 拉普拉斯居中度研究概述	★ 信息居中度研究簡要回顧

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在本篇論文裡，我們在不同的圖上考慮目標集選擇問題(target set selection problem)。
在第二章，我們證明了在任意閾值(thresholds)的區塊仙人掌圖(block-cactus graphs)以及閾值小於等於2的弦圖(chordal graph)上，目標集選擇問題可以在線性時間內解決。當考慮閾值為2的漢米圖(Hamming graphs)時，我們可以給出一個最佳解。在第三章，我們考慮的是閾值為2的cycle permutation graphs和廣義彼得森圖形。在第四章，對於閾值為3的torus cordalis 與torus serpentinus的最佳解，提出一個改進的上界。在第五章，我們考慮以下幾種蜂巢狀網路在strict majority thresholds下的目標集選擇問題：蜂巢式網格(honeycomb mesh)、蜂巢式環形曲面(honeycomb torus)、蜂巢式矩形環形曲面(honeycomb rectangular torus)、蜂巢式菱形環形曲面(honeycomb rhombic torus)、廣義蜂巢式環形曲面(generalized honeycomb torus)以及六角網格(hexagonal grids)。在第六章，我們研究多邊形拼圖在strict majority thresholds下的目標集選擇問題。

摘要(英)

In this thesis, We are interested in the target set selection problem on different kinds of graphs.
In Chapter 2, we show that if G is a block-cactus graph with general thresholds, then the TARGET SET SELECTION problem can be solved in linear time. When G is a chordal graph with thresholds heta(v) leq 2 for each vertex v in G, then the problem can also be solved in linear time. We precisely determine an optimal target set for a Hamming graph G with constant threshold heta(v) = 2 for each vertex v in G.
In Chapter 3, we determine an optimal target set for (G,2) where G is a cycle permutation graph or a generalized Petersen graph.
In Chapter 4, we present some improved upper bounds and exact values for the parameters min-seed(C_m oslash C_n,3) and min-seed(C_m otimes C_n,3).
In Chapter 5, we study the TARGET SET SELECTION problem under strict majority thresholds on different kinds of honeycomb networks such as honeycomb mesh HM_t, honeycomb torus HT_t, honeycomb rectangular torus HReT(m,n), honeycomb rhombic torus HRoT(m,n), generalized honeycomb rectangular torus GHT(m,n,d) and three kinds of hexagonal grids (planar, cylindrical, and toroidal).
In Chapter 6, we determine minimum target sets for several tilings of the plane under strict majority threshold.

關鍵字(中)

★ 區塊仙人掌圖
★ 擴散
★ 社群網路
★ 目標集選擇
★ 六角網格
★ 弦圖
★ 漢米圖
★ 環面
★ 蜂巢狀網路

關鍵字(英)

★ honeycomb networks
★ chordal graph
★ block-cactus graph
★ diffusion
★ social networks
★ target set selection
★ tori
★ Hamming graph
★ hexagonal grid

論文目次

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
1 Introduction and Preliminaries 1
1.1 Target set selection problem . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sequential activation process . . . . . . . . . . . . . . . . . . . . . . . 6
2 Block-cactus graphs, chordal graphs and Hamming graphs 9
2.1 Introduction and preliminaries . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Block-cactus graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Chordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Hamming graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Cycle Permutation Graphs and Generalized Petersen Graphs 22
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Cycle permutation graphs and generalized Petersen graphs . . . . . . 24
4 Torus Cordalis and Torus Serpentinus 26
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Torus cordalis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Torus serpentinus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Honeycomb Networks 46
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 Honeycomb mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Generalized honeycomb rectangular torus . . . . . . . . . . . . . . . . 50
5.4 Hexagonal grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 Tilings in the plane 64
6.1 Tetragon and Octagon . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2 Hexagon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.3 Pentagon and Heptagon . . . . . . . . . . . . . . . . . . . . . . . . . 72
Bibliography 76
Appendix 80
A Graphical illustrations in Chapter 4 80
B Graphical illustrations in Chapter 5 93
C Graphical illustrations in Chapter 6 99

參考文獻

[1] E. Ackerman, O. Ben-Zwi, G. Wolfovitz, Combinatorial model and bounds for
target set selection, Theoretical Computer Science 411 (2010) 4017-4022.
[2] S. S. Adams, D. S. Troxell, S. L. Zinnen, Dynamic monopolies and feedback
vertex sets in hexagonal grids, Computers and Mathematics with Applications
62 (2011) 4049-4057.
[3] B. Alspach, M. Dean, Honeycomb toroidal graphs are Caley graphs, Information
Processing Letters 109 (2009) 705-708.
[4] O. Ben-Zwi, D. Hermelin, D. Lokshtanov, I. Newman, Treewidth governs the
complexity of target set selection, Discrete Optimization 8 (2011) 87-96.
[5] E. Berger, Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83
(2001) 191-200.
[6] C. C. Centeno, M. C. Dourado, L. Draque Penso, D. Rautenbach, J. L. Szwarc-
fiter, Irreversible conversion of graphs, Theoretical Computer Science 412 (2011)
3693-3700.
[7] C. L. Chang, Y. D. Lyuu, Bounding the number of tolerable faults in majority-
based systems, Lecture Notes in Computer Science 6078 (2010) 109-119.
[8] G. Chartrand, F. Harary, Planar Permutation Graphs, Ann. Inst. Henri. Poincar¶e
Sect. B 3 (1967) 433-438.
[9] G. Chartrand, J. B. Frechen, On the Chromatic Number of Permutation Graphs.
In: F. Harary (ed.): Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, February 1968. Academic Press,
New York, pages 21-24, 1969.
[10] N. Chen, On the approximability of influence in social networks, SIAM Journal
on Discrete Mathematics, 23 (2009) 1400-1415.
[11] H-J Cho, L-Y Hsu, Generalized honeycomb torus, Information Processing Letters
86 (2003) 185-190.
[12] H. S. M. Coxeter, Self-Dual Configurations and Regular Graphs, Bull. Amer.
Math. Soc. 56 (1950) 413-455.
[13] G. A. Dirac, On Rigid Circuit Graphs, Abh. Math. Sem. Univ. Hamburg, 25
(1961) 71-76.
[14] P. Domingos, M. Richardson, Mining the network value of customers, in Pro-
ceedings of ACM SIGKDD 2001, San Francisco, pages 57-66, 2001.
[15] P. A. Dreyer, Applications and Variations of Domination in Graphs, Ph.D. thesis,
Rutgers University, Piscataway, NJ, 2000.
[16] P. A. Dreyer, F. S. Roberts, Irreversible k-threshold processes: Graph-theoretical
threshold models of the spread of disease and of opinion, Discrete Applied Math.
157 (2009) 1615-1627.
[17] P. Festa, P. M. Pardalos, M. G. C. Resende, Feedback set problems, in Handbook
of Combinatorial Optimization, Supplement Vol. A, Kluwer Academic Publish-
ers, (2000) 209-259.
[18] P. Flocchini, F. Geurts, N. Santoro, Optimal irreversible dynamos in chordal
rings, Discrete Applied Mathematics 113 (2001) 23-42.
[19] P. Flocchini, R. Kr¶alovi·c, P. Ru¶zi·cka, A. Roncato, N. Santoro. On time versus
size for monotone dynamic monopolies in regular topologies, Journal of Discrete
Algorithms 1 (2003) 129-150.
[20] P. Flocchini, E. Lodi, F. Luccio, L. Pagli, N. Santoro, Dynamic monopolies in
tori, Discrete Applied Mathematics 137 (2004) 197-212.
[21] P. Flocchini, Contamination and Decontamination in Majority-Based Systems,
Journal of Cellular Automata 4 (2009) 183-200.
[22] D. R. Fulkerson, O. A. Gross, Incidence Matrices and Interval Graphs, Pacific
Journal of Mathematics, 15 (1965) 835-855.
[23] W. T. Huang, On the Spread of Viruses on Torus Cordalis Networks, Master’’s
Thesis, Department of Mathematics, National Central University, Taiwan, 2010.
[24] W. Imrich, S. Klav·zar, Product Graphs: Structure and Recognition, John Wiley &
Sons, 2000.
[25] R. M. Karp, Reducibility among combinatorial problems, Complexity of Com-
puter Computations 40 (1972) 85-103.
[26] D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of in°uence through a
social network, in Proceedings of the 9th ACM SIGKDD international conference
on Knowledge discovery and data mining, pages 137-146, 2003.
[27] D. Kempe, J. Kleinberg, E. Tardos, Influential nodes in a diffusion model for
social networks, in: Proceedings of the 32th International Colloquium on Au-
tomata, Languages and Programming, pages 1127-1138, 2005.
[28] K. Khoshkhah, H. Soltani, M. Zaker, On dynamic monopolies of graphs:
The average and strict majority thresholds, Discrete Optimization (2012),
doi:10.1016/j.disopt.2012.02.001
[29] D. M. Kilgour, Approval balloting for muti-winner elections, in J. Laslier &
M. R. Sanver (Eds.), Handbook on approval voting, pages 105-124, Heidelberg,
Springer.
[30] S. Kutten, D. Peleg, Fault-local distributed mending, in: Proceedings of the 36th
IEEE Symposium on Foundations of Computer Science, 1995.
[31] N. Linial, D. Peleg, Y. Rabinovich, M. Saks, Sphere packing and local majorities
in graphs, in: Second ISTCS, IEEE Computer Society Press, Silver Spring, MD,
pages 141-149, 1993.
[32] F. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies,
Information Processing Letters 66 (1998) 59-64.
[33] F. Luccio, L. Pagli, H. Sanossian. Irreversible dynamos in butterflies, 6th Int.
Coll. on Structural Information and Communication Complexity (SIROCCO),
pages 204-218, 1999.
[34] B. Parhami, D-M Kwai, A Unified Formulation of Honeycomb and Diamond
Networks, IEEE Transactions on paralel and distributed systems 12 (2001) 74-
80.
[35] D. Peleg, Size bounds for dynamic monopolies, Discrete Applied Mathematics 86
(1998) 263-273.
[36] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theo-
retical Computer Science 282 (2002) 231-257.
[37] D. A. Pike, Y. Zou, Decycling Cartesian products of two cycles, SIAM Journal
on Discrete Mathematics, 19 (2005) 651-663.
[38] M. Richardson, P. Domingos, Mining knowledge-sharing sites for viral marketing,
in Proceedings of the 8th ACM SIGKDD, Edmonton, Canada, pages 61-70, 2002.
[39] F. S. Roberts, Challenges for discrete mathematics and theoretical computer sci-
ence in the defense against bioterrorism, in Bioterrorism: Mathematical Model-
ing Applications in Homeland Security, Frontiers Appl. Mathem. 28, H. T. Banks
and C. Castillo-Chavez, eds., SIAM, Philadelphia, pages 1-34, 2003.
[40] F. S. Roberts, Graph-theoretical problems arising from defending against
bioterrorism and controlling the spread of fires, in Proceedings of the DI-
MACS/DIMATIA/Renyi Combinatorial Challenges Conference, Piscataway, NJ,
2006.
[41] D. J. Rose, R. E. Tarjan, G. S. Lueker, Algorithmic Aspects of Vertex Elimination
on Graphs, SIAM Journal on Computing, 5 (1976) 266-283.
[42] I. Stojmenovic, Honeycomb networks: Topological properties and communication
algorithms, IEEE Trans. Parallel Distributed Systems, 8 (1997) 1036-1042.
[43] S. Stueckle, R. D. Ringeisen, Generalized Petersen graphs which are cycle per-
mutation graphs, Journal of Combinatorial Theory B, 37 (1984) 142-150.
[44] R. E. Tarjan, M. Yannakakis, Simple linear-time algorithms to test chordality of
graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs,
SIAM Journal on Computing, 13 (1984) 566-579.
[45] M. Watkins, A Theorem on Tait Colourings with an Application to the General-
ized Petersen Graphs, Journal of Combinatorial Theory, 6 (1969) 152-164.
[46] D. J. Watts, The accidental influentials, Harvard Business Review, 85 (2007)
22-23.
[47] X. Yang, The diameter of honeycomb rhombic tori, Applied Mathematics Letters
17 (2004) 167-172.
[48] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete
Mathematics 312 (2012) 1136-1143.

指導教授

葉鴻國(Hong-Gwa Yeh)

審核日期

2012-6-28

推文